[백준] 1541번: 잃어버린 괄호 [C++]

 

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

문제 링크: https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

 

 

【 풀이 】

 

문자열을 잘 쪼개서 숫자로 변환시켜 적절히 더하는 문제이다.

'-' 기호가 처음 나온 경우, 그 위치 기준 뒤에 있는 모든 숫자들을 빼면 식의 값을 최소로 만들 수 있다.

원리는 다음과 같다.

 

• 55 - 50 + 40 => 55 - (50 + 40)
• 50 - 40 + 30 - 20 + 10 => 50 - (40 + 30) - (20 + 10)
• 9 - 8 + 6 + 5 - 3 =>  9 - (8 + 6 + 5) - 3
• 5 + 5 + 6 - 8 + 9 + 10 => 5 + 5 + 6 - (8 + 9 + 10)

 

 

【 코드 】

 

#include<iostream>
#include<string>
using namespace std;

string str;
int main(void) {
	string num = "";		//	숫자를 저장할 문자열 변수
	bool minus=false;		//	'-' 기호가 나왔는지를 확인하는 변수
	int sum = 0;		//	출력하게될 결과
	cin >> str;
    
	for (int i = 0; i <= str.size(); i++) {
		if (str[i] == '+' || str[i] == '-' || str[i] == '\0') {	
        	//	기호일 경우
			if (minus == true) {
            		//	'-' 기호가 한번이라도 나왔다면 그 뒤의 숫자들은 모두 빼주면 된다.
				sum -= stoi(num);
				num = "";		//	꼭 초기화
			}
			else if (minus == false) {
            		//	반대로 '-' 기호가 아직 나오지 않았다면, 나오기 전까지는 모두 더해주면 된다.
				sum += stoi(num);
				num = "";		//	꼭 초기화
			}
		}
		else {		//	숫자일 경우
			num += str[i];
		}
		if (str[i] == '-') {
        	//	'-' 기호가 나왔을 경우
         	//	이 구문이 처음에 있으면 '-' 기호가 나오기 바로 전의 숫자가 음수로 더해지는 문제가 발생한다.
			minus = true;
		}
	}
	cout << sum;
	return 0;
}