Baekjoon 1541 잃어버린 괄호

Link https://www.acmicpc.net/problem/1541

소스결과 1988 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘

 

설명

양수, +, -로 구성된 식에 적절한 괄호를 추가해 결과 값을 최소로 만드는 경우의 값을 출력한다.

 

-가 등장하는 순간 그 뒤에 + 식을 전부 괄호로 묶으면 괄호 안의 결과 값을 빼는 모습이 된다.

즉 -가 등장하기 전 까지의 합과, 등장한 후의 합을 빼면 그 결과 값은 항상 최소값이 된다.

굳이 어려운 점을 따지자면 문자열을 입력받아 연산자와 피연산자를 나누는게 어려운부분..?

 

알고리즘

1. 문자열을 입력받는다.

2. 문자열의 0번 인덱스부터 문자열의 길이만큼 반복한다.

 2 - 1. 현재 위치의 문자 값이 숫자인 경우 연산자를 만나기 전 까지 숫자로 바꾸며, 10진법에 맞는 형태의 계산 결과를 띈다.

 2 - 2. 현재 위치의 문자가 + 이면서, -가 발견되지 않았다면 앞 계산결과에 더한 후, 계산 결과로 저장한다.

 2 - 3. 현재 위치의 문자가 + 이지만, -가 발견이 됬었다면, 발견 이후의 계산 결과에 2 - 1 과정을 통해 구해진 값을 더한다.

 2 - 4. -가 발견이 되면, - 발견 플래그를 세운다.

3. 2에서 구한 발견 이전의 값에서 발견 이후의 값을 뺀 결과를 출력한다.

 

소스코드

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

const int MAX = 50;
char input[MAX+1];

int main()
{
	cin >> input;

	stack<int> opnd;
	bool foundMinus = false;

	int digit = 0;
	char oper = '+';
	for (int i = 0; true; i++)
	{
		if (input[i] == 0)
		{
			if (foundMinus)
				digit *= -1;

			opnd.push(digit);

			while (opnd.size() > 1)
			{
				int opnd1 = opnd.top(); opnd.pop();
				int opnd2 = opnd.top(); opnd.pop();

				opnd.push(opnd1 + opnd2);
			}
			break;
		}
		else if ('0' <= input[i] && input[i] <= '9')
			digit = (digit * 10) + (input[i] - '0');
		else
		{
			oper = input[i];

			if (foundMinus)
				digit *= -1;

			if (oper == '-')
				foundMinus = true;

			opnd.push(digit);
			digit = 0;
		}
	}

	cout << opnd.top(); 

	return 0;
}