[G5] 백준 2504번 괄호의 값 C++ 스택

리뷰

 

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

스택 문제인건 알겠으나 괄호의 배치에 따른 정답 연산에 애먹은 문제

 

 

전역 변수

• s : 입력되는 괄호의 정보를 저장할 문자열 변수
• stack : 괄호의 여닫기를 체크하기 위해 스택으로 사용할 문자 타입의 벡터

 

함수

없음

 

 

문제풀이

1. 괄호로 이루어진 문자열을 s에 입력 받아준다.
2. 정답을 출력할 변수 ans를 0으로, 시뮬레이션에 사용할 변수 temp를 1로 초기화 한다.
3. 문자열 s의 길이만큼의 반복문을 실행해 준다.
4. 만약 s[i]가 '(', '['라면 temp에 2배, 3배를 곱해주고 스택에 괄호를 추가해 준다.
5. 만약 s[i]가 ')'라면 우선 스택이 비어있거나 스택의 맨 위가 '('가 아니라면 탐색을 중지하고 0을 출력한다.
6. 맞다면 s[i - 1]이 '(' 라면 ans에 temp의 값을 더해준다.
7. ans에 더해준 것과 상관 없이 temp를 2로 나누어 주고 스택에서 괄호를 빼준다.
8. 만약 s[i]가 ']'라면 스택이 비어있거나 스택의 맨 위가 '['가 아니라면 탐색을 중지하고 0을 출력한다.
9. 맞다면 s[i - 1]이 '[' 라면 ans에 temp의 값을 더해준다.
10. ans에 더해준 것과 상관 없이 temp를 3으로 나누어 주고 스택에서 괄호를 빼준다.
11. 위 작업을 마친 후 만약 스택이 빈 상태가 아니라면 0을, 빈 상태라면 ans에 저장된 값을 출력해 준다.

 

참고 사항

괄호를 모두 순회했을 때 이상이 없더라도 연산을 마친 후 스택에 괄호가 남아있다면 올바른 괄호열이 아니다.

temp를 사용한 연산은 사칙연산 중 분배 법칙을 활용한 것이다.

 

 

정답 코드

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

string s;
vector<char> stack;

int main() {
	cin >> s;
	int ans = 0, temp = 1;
	for (int i = 0; i < s.size(); ++i) {
		switch (s[i]) {
		case '(':
			temp *= 2;
			stack.push_back(s[i]);
			break;
		case '[':
			temp *= 3;
			stack.push_back(s[i]);
			break;
		case ')':
			if (stack.empty() || stack.back() != '(') {
				cout << 0;
				return 0;
			}
			if (s[i - 1] == '(') ans += temp;
			temp /= 2;
			stack.pop_back();
			break;
		case ']':
			if (stack.empty() || stack.back() != '[') {
				cout << 0;
				return 0;
			}
			if (s[i - 1] == '[') ans += temp;
			temp /= 3;
			stack.pop_back();
			break;
		default:
			cout << 0;
			return 0;
		}
	}
	if (!stack.empty()) cout << 0;
	else cout << ans;
}