[백준/c++] 2504 - 괄호의 값

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

2504번: 괄호의 값

---

1) 풀이

분명 문제를 내 손으로 직접 풀었음에도 불구하고

다시 풀었을 때, 유난히 어려운 문제들이 몇개 있는데

그 몇개 중 하나가 이 문제였다😭

 

이틀이 걸려서 문제를 겨우 맞혔을 때 정말 뿌듯하기도 했지만

자꾸 98%에서 틀렸다고 나온 이유가 딱 한가지의 예외처리를

해주지 않아서 라는 걸 알게 됐을 때 얼마나 허무하던지....

 

아무튼, 문제는 입력된 문자열이 올바른 괄호열일때,

그 괄호열에 알맞은 계산을 하여 최종 값을 출력하는 것을 목표로 한다.

아래는 괄호 값 계산하는 방법을 그대로 복사해왔다. 

 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

푸는 데에는 여러가지 방식이 있겠지만.

나는 스택을 하나 만들어서 여는 괄호( [ 들을 넣고

닫는 괄호 ) ] 가 나올 때 각 값을 적절하게 계산해준 뒤

그 숫자들을 스택에 함께 저장하는 형식으로 풀었다.

ex. 스택 내부의 모습이 정말 이렇지는 않겠지만, 굳이 구현해서 설명하자면

((2[3 와 같이 여는 괄호와 계산해준 값을 스택에 함께 넣어놓는다는 의미이다.

 

입력된 괄호열의 문자 하나하나를 읽어가면서 적절하게 처리해주면 되는데

우선, 여는 괄호가 읽힐 때는 그냥 스택에 push 해주면 된다.

 

문제는 닫는 괄호가 읽힐 때인데, 숫자 계산과 괄호열이 올바른지 아닌지를

함께 판단해야 하기 때문에 처리할 사항이 좀 많다.

같은 사항을 )와 ] 각각의 상황으로 적어주면 되기 때문에 설명은 ) 기준으로만 하겠다.

 

1. 올바르지 않은 괄호열일 경우

- 0을 출력하고 프로그램을 바로 종료한다

1) 스택이 비어있을 때

2) 아래의 상황 속 몇몇 경우

2. 스택의 top이 ( 일 때 

-스택에 있는 여는 괄호 ( 를 pop하고 계산한 값 2를 넣어준다

3. 나머지

1) 스택의 top이 [인 경우 - 1과 같이 처리

2) 스택의 top이 숫자인 경우 - (가 나올때까지 임시 변수 sum 값에 더해주고 pop하는 반복문

이때 나오는 숫자 값들은 서로가 서로를 감싼 괄호가 아니라 () 괄호 안에 나란히 들어있던 개별의 괄호들이 계산된 것이므로, 각각을 모두 더해주는 처리를 해야한다.(위에 복사해둔 괄호값 계산 조건에서 5번 참고)

*pop하고 스택이 빌 경우 올바르지 않은 괄호열이므로 1과 같이 처리)

3) 반복문이 끝나면 스택의 top 이 ( 인 경우이므로 pop 해주고 지금까지의 값을 더한 sum에 2를 곱해준다

위에 복사해둔 괄호값 계산 조건에서 3에 해당한다. 안에 있는 값들에 곱하기 2에 해줘야 하는 상황.

4) 만약 스택이 비었다면, 정답 변수(정답으로 출력할 변수)에 더해주면 되고

괄호열들을 제일 크게 감싸고 있던 괄호열이 끝났다는 뜻. 그 다음에 읽을 괄호열이 남아있다고 하더라도, 이전의 괄호열에 영향을 끼치지 않음

스택이 비지 않았다면, 스택에 push 해주면 된다.

 

]의 경우에도 똑같은 방식으로 처리해주고, 

마지막에 스택이 빌 때까지 스택의 top을 정답 변수에 더해주고

pop해주면 되는데, 이때 스택의 top이 숫자가 아니라 여는 괄호라면

0을 출력하고 종료한다.

 

올바른 경우에는 정답 변수를 출력해주면 된다.

 

정답을 내기까지 시행착오가 많았던지라

다른 문제들에 비해 설명이 다소 장황해지는 경향이 있는 것 같다.

나중에 이 풀이를 보고 좀 부족하다고 생각되는 부분이 있다면

보충해놓도록 하겠다. 지금은 머리가 복잡해서 더이상은....😱

최대한 보기 좋게 소스코드에 주석으로 달아놓을테니 참고했으면 좋겠다.

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
string s;
stack<int>st; //여는 괄호와 계산값을 저장할 스택. 괄호는 char 형이지만 들어가거나 나올때 int 값으로 자동계산되니 상관없다
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	int ans = 0; //정답 변수
	for (auto c : s) { //입력된 괄호열의 문자 하나하나를 읽는다
		int sum = 0; //임시변수 sum
		if (c == '(' || c == '[') { //여는 괄호일때
			st.push(c);
		}
		else if (c == ')') {
			if (st.empty()) { //스택이 빈 경우. 올바르지 못한 괄호열.
				cout << 0 << '\n';
				return 0;
			}
			else if (st.top() == '(') { //괄호 하나가 완성
				st.pop();
				st.push(2);
			}
			else {
				while (st.top() !='(') { //(가 나올때까지 반복문
					if (st.top() == '[') { //올바르지 못한 괄호열.
						cout << 0 << '\n';
						return 0;
					}
					sum += st.top(); //임시변수에 나란히 있는 값들을 더해준다
					st.pop();
					if (st.empty()) {
						cout << 0 << '\n';
						return 0;
					}
				}
				st.pop(); // ( 를 pop
				sum = sum * 2; //()가 sum 값들을 감싸고 있는 형태였으므로. ->(x)
				if (st.empty()) {
					ans += sum;
				}
				else st.push(sum);
			}
		}
		else if (c == ']') {
			if (st.empty()) { //스택이 빈 경우. 올바르지 못한 괄호열.
				cout << 0 << '\n';
				return 0;
			}
			else if (st.top() == '[') {//괄호 하나가 완성
				st.pop();
				st.push(3);
			}
			else {
				while (st.top() != '[') {  //[가 나올때까지 반복문
					if (st.top() == '(') {//올바르지 못한 괄호열.
						cout << 0 << '\n';
						return 0;
					}
					sum += st.top();//임시변수에 나란히 있는 값들을 더해준다
					st.pop();
					if (st.empty()) {
						cout << 0 << '\n';
						return 0;
					}
				}
				st.pop(); // [ 를 pop
				sum = sum * 3; //[]가 sum 값들을 감싸고 있는 형태였으므로. ->[x]
				if (st.empty()) {
					ans += sum;
				}
				else st.push(sum);
			}
		}

	}
	while (!st.empty()) {
		if (st.top() == '[' || st.top() == '(') { //중간에 여는 괄호가 나오면 짝지어지지 못한 것임. 즉, 올바르지 못한 괄호열.
			cout << 0 << '\n';
			return 0;
		}
		ans += st.top();
		st.pop();
	}
	cout << ans << '\n'; 
}

3) 참고자료