🙇‍♀️[Silver II] 잃어버린 괄호 - 1541

문제 링크

성능 요약

메모리: 2028 KB, 시간: 0 ms

분류

그리디 알고리즘, 수학, 파싱, 문자열

제출 일자

2023년 12월 29일 16:53:54

문제 설명

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

🚀풀이

먼저 수식을 string으로 받고 숫자와 기호를 구분해야한다.

숫자를 저장할 배열과 기호를 저장할 배열을 만들고 각 배열을 채워준다.

문제를 해결할 로직을 이 이후인데 -기호를 발견하면 다음 -기호를 만날때까지 임시적으로 값을 더해준다.

그 다음 결과 값에 임시값을 빼준다.

+를 만나면 그냥 결과값에 더해주면 된다.

void solve()
{
	int pos = 0, pos2 = 0;
	res = numbers[pos];
	while (true)
	{
		if (signs[pos2] == "-")
		{
			pos2++;

			int temp = 0;
			while (signs[pos2] != "-" && pos2 < p2)
			{
				pos++;
				temp += numbers[pos];
				pos2++;
			}
			pos++;
			temp += numbers[pos];
			res -= temp;
		}
		else if (signs[pos2] == "+")
		{
			pos++;
			pos2++;
			res += numbers[pos];
		}

		if (pos == p1)
			break;
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

string str;
int numbers[51];
string signs[51];

int p1 = 0, p2 = 0, res = 0;
// -가 나오면 다음 -가 나올 때까지 그 사이는 다 더해주고 빼기

void setting()
{
	cin >> str;

	int temp = 0;
	for (int i = 0; i < str.size(); ++i)
	{
		if (str[i] != '+' && str[i] != '-')
		{
			temp *= 10;
			temp += str[i] - '0';
		}
		else
		{
			numbers[p1] = temp;
			p1++;
			signs[p2] = str[i];
			p2++;

			temp = 0;
		}
	}
	numbers[p1] = temp;
}

void solve()
{
	int pos = 0, pos2 = 0;
	res = numbers[pos];
	while (true)
	{
		if (signs[pos2] == "-")
		{
			pos2++;

			int temp = 0;
			while (signs[pos2] != "-" && pos2 < p2)
			{
				pos++;
				temp += numbers[pos];
				pos2++;
			}
			pos++;
			temp += numbers[pos];
			res -= temp;
		}
		else if (signs[pos2] == "+")
		{
			pos++;
			pos2++;
			res += numbers[pos];
		}

		if (pos == p1)
			break;
	}

	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고