[백준] 1541_잃어버린 괄호 (C++)

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

1541번: 잃어버린 괄호

 

처음에 왜 55-50+40이 -35가 나오는지 몰랐다. 

그런데 식을 보니깐

마이너스가 나오려면 마이너스가 커야 하기 때문에 

55-(50+40)하면 -35가 나온다는 걸 깨달았다. 

 

수업시간에 깨달아서 좀 진정하고 코드를 짰다. 

역시 알고리즘 먼저 생각하고 짜니깐.

짜는건 오래 안 걸린다...

 

알고리즘

• 입력을 받는다
• stringstream으로 숫자 파싱한다. 
• 파싱한 숫자가 0보다 크다면(양수)
  • sum(마이너스 일 때 더한 수)가 0이면 push
  • sum이 0이 아니라면, 
    • 앞에 마이너스가 있어서 마이너스 할 것을 더하고 있다면 sum더하기 ( ex, -20+30일 경우)
    • 그냥 양수가 나온 것이라면, push (ex, +50+60+70)
• 0보다 작다면(음수)
  • 마이너스가 나온 것이 처음 or 마이너스 시작이면
    • check true로 하고(시작했다는 것을 알림)
    • sum에 num 더하기
  • 앞에 마이너스가 있어서 더하고 있었는데 다음 마이너스가 나온 것이라면 (ex, -20 +30 40 -30)
    • 더한 값 전부 -1곱해서 push
    • sum을 새로 업데이트 

 

그냥 생각하면 쉬웠는데,,

조금 더러운 코드가 된게 아닌가 싶다...

 

#include <iostream>
#include<sstream>
#include<string>
#include <stack>

using namespace std;
int main() {
	stringstream ss;
	string input;
	stack<int> number;

	int num;
	int sum = 0;
	cin >> input;
	ss.str(input);
	bool check = false;
	while (ss >> num) {
		if (num > 0) {
			if (sum == 0) {
				number.push(num);
			}
			else {
				if (!check) {
					number.push(num);
				}
				else {
					sum += num;
				}
			}
		}
		else {
			if (!check) {
				check = true;
				sum += num * (-1);
			}
			else {
				number.push((-1)*(sum));
				sum = num * (-1);
				check = true;
			}	
		}
	}
	if(check)
		number.push((-1)*(sum));
	int output = 0;
	for (int i = 0; !number.empty(); i++) {
		output += number.top();
		number.pop();
	}
	cout << output;
	return 0;
}