[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘

매우 간단한 문제이다. 

마이너스가 한번 뜨면 그 이후로는 무조건 음수로 만들수 있다.

WHY? 그 이후에 오는

연산자가 + 이면 괄호로 합쳐서 음수로 만들수 있고,

연산자가 - 라면 그 이후에 괄호를 칠 수 있고,

이후의 식이 또 다시 음수가 되기 때문이다.

 

예를 들어 

10 - 20 + 30 + 40 - 50 + 60 이라고 하자.

다음과 괄호를 칠 수 있다.

10 -(20 + 30 + 40) - (50 + 60)

 

10 -20 + 30 + 40 + 50 + 60 이라면?

10 -(20 + 30 + 40 + 50 + 60)

 

#include <iostream>

char	buffer[1024] = { 0 , };
char	operators[100] = { 0 , };
int		Numbers[100] = { 0 , };
int		tempNumber = 0;
int		Ans = 0;

int		FirstMinus = -1;
int		operatorCount = 0;
int		NumberCount = 0;

int main()
{
	std::cin.tie(0);
	std::cout.tie(0);

	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);


	std::cin >> buffer;
	for (int i = 0; i < 1024; ++i)
	{
		if (0 == buffer[i])
		{
			Numbers[NumberCount++] = tempNumber;
			break;
		}
		

		if ('-' == buffer[i] || '+' == buffer[i])
		{
			Numbers[NumberCount++] = tempNumber;
			tempNumber = 0;
			operators[operatorCount++] = buffer[i];
			continue;
		}

		tempNumber = tempNumber * 10 + buffer[i] - 48;
	}

	FirstMinus = NumberCount;

	for (int i = 0; i < operatorCount; ++i)
	{
		if ('-' == operators[i])
		{
			FirstMinus = i;
			break;
		}		
	}

	for (int i = 0; i <= FirstMinus; ++i)
		Ans += Numbers[i];

	for (int i = FirstMinus + 1; i < NumberCount; ++i)
		Ans -= Numbers[i];

	std::cout << Ans << std::endl;
	

	return 0;
}