[백준 1541 - 읽어버린 괄호] string을 다양한 형식으로 받아내서 처리하기

문제 출처

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

---

문제 내용

문제

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

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

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

입력

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

출력

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

---

접근

무조건 정답을 출력하는 논리는 간단하다. 입력에서 '-'부호가 등장한다면 그 후의 값은 전부 마이너스로 처리하면 된다.

왜냐하면 '-'부호 이후에 '+'가 오든 '-'가 오든 괄호를 통해서 어떻게든 음수 처리를 할 수 있다. 문제의 목적은 식의 값을 최소로 만드는 것이기 때문에 음수 처리를 하는 것이 항상 옳다.

 

그래서 아주 쉽게 풀어낼 수 있을 줄 알았는데, 문제는 문자열 처리였다. 입력으로 최대 50글자인 문자열이 들어오는데 이를 숫자와 부호로 구분해야 한다. 한글자 한글자 받아서 처리하면 어떻게든 되겠지만 그러고 싶지 않았다. 비효율적일 뿐더러 나중에 비슷한 문제가 나왔을 때 디버깅 등 문제에 너무 쉽게 노출되기 때문이다. 그렇게 인터넷을 뒤지다가 알아낸 것이 stringstream 이었다.

 

stringstream을 이용해 문자열을 int와 char으로 구분해서 받아내는 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <sstream> // stringstream은 의외로 sstream으로 표기한다.

using namespace std;

int main() {
	string str;
	int num;
	char sign;
	
	cin >> str;
		
	stringstream ss(str);
		
	while(ss >> num) // 이러한 출력방식에 유의할 것.
	{
		cout << num << endl;
		
		if (ss >> sign) {
			cout << sign << endl;	
		}		
	}
}

---

풀이

문자열 처리 문제를 처리했으니 풀이는 아주 쉬워진다. 숫자를 계속 받아내면서 이전에 '-' 부호를 받아낸 적 있는지 돌이켜본다. 한번이라도 '-' 부호를 받아낸 적이 있다면 그 이후부터는 sum에서 음수로 처리한다. 그 논리는 위에 서술한 바와 같다.

---

코드

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

vector<int> numbers;
vector<char> signs;

int main() {
	string str; // 전체 식을 받아낼 스트링 변수
	
	int num; // 임시로 숫자를 저장할 변수
	char sign; // 임시로 부호를 저장할 변수
	bool isInMinus = false; // 마이너스 부호가 나왔는지 알려주는 flag
	int sum = 0; // 최소 합을 담을 변수
	
	cin >> str;
		
	stringstream ss(str);
		
	while(ss >> num) // 받아낼 숫자가 없을 때까지 반복한다.
	{
		if (isInMinus == false) // 마이너스 부호가 나온 적이 없다면 결과값에 더한다.
			sum += num;
		else
			sum -= num;
		
		if (ss >> sign) { // 맨끝이라서 부호가 더이상 없다면 실행하지 않는다.
			if (isInMinus == false && sign == '-') isInMinus = true; // 마이너스가 등장했다면 flag를 바꿔준다. 
		}
	}
	
	cout << sum << "\n";
}

---

반성

• stringstream 클래스를 알지 못했고 그로인해 문자열 처리에 많은 시간을 허비했다.
• 하지만 문제의 근본적인 논리 문제는 간단히 해결할 수 있었기에 코드를 직관적으로 설계할 수 있었다.