ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

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

Posted on Mar 2, 2021 #그리디   #Algorithm  

1541 | 잃어버린 괄호

🙋‍♀️ 문제

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

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

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

🙌 입출력

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

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

🙋‍♂️ 예제 입출력

55-50+40

-35

🚀 코드

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

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string str;
	cin >> str;
	list<int> num;
	list<char> ope;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '-' || str[i] == '+') {
			ope.push_back(str[i]);
		}
		else {
			// 숫자이면
			string number = "";
			while (str[i] >= '0' && str[i] <= '9') {
				number += str[i];
				i++;
			}
			i--;
			int realNum = 0;
			int k = 1;
			for (int j = number.length() - 1; j >= 0; j--) {
				realNum += (number[j] - '0') * k;
				k *= 10;
			}
			num.push_back(realNum);
		}
	}
	int rst = num.front();
	num.pop_front();
	bool flag = false;
	while (!ope.empty()) {
		char oper = ope.front();
		ope.pop_front();
		if (oper == '-') {
			flag = true;
		}

		if (flag == true) {
			rst -= num.front();
			num.pop_front();
		}
		else {
			rst += num.front();
			num.pop_front();
		}
	}
	cout << rst;

	return 0;
}

🌠 메모

처음에는 알고리즘을 제대로 생각해 내지 못해서 -뒤에 +가 바로 나올 경우에만 괄호를 치는 방식으로 풀었다가 틀렸다.

정확한 접근 방식은

-를 만나는 순간 그 뒤의 모든 값들을 빼주면 된다.

따라서 -를 만나면 flag를 true로 바꿔주고 이후의 값들은 모두 빼주면 된다. 괄호를 적절히 여러 번 쓰면 되기 때문이다.



# 카테고리