백준 2504 괄호의 값 C++ 풀이

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

2504번: 괄호의 값

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

 

이 문제는 stack 자료구조를 사용하여 괄호를 이용하여 숫자 계산을 하는 문제이다.

 

문제의 포인트

괄호가 닫힐 때 곱하기 처리를 하는 것이 아닌 먼저 처리를 하는 생각의 전환을 할 수 있는가?

문제 이해

우선 이 문제는 괄호가 정상적으로 닫히는지 확인하여야 한다. 그 후 괄호를 계산하게 되는데,

1)    ()가 2, []가 3으로 취급

2)    ()안에 계산된 값이(다른 괄호가) 들어있다면 x2, []안에 계산된 값이(다른 괄호가) 들어있다면 x3

3)    ()[]이렇게 괄호가 연달아 있는 경우 서로를 더해준다.

와 같은 규칙들이 있다.

문제 설명

스택과, 임시 정수 공간 temp, 실제 출력해줄 답인 answer 정수 공간을 선언해준다.

 

(,[가 입력되면 스택 자료형에 넣고, 곱하기를 계산해준다. (나중에 나누기를 통해 상쇄 시키면 됨)

 

),]가 입력 될 시, 유효한 여는 괄호가 없는 경우(스택이 비었거나, 해당 괄호의 여는 괄호가 없는 경우)

답을 바로 0으로 설정 후 예외처리를 해준다.

 

만약 괄호가 유효하고, 바로 뒤에 여는 괄호가 있을 경우 현재까지의 계산값을 실제 출력할 공간에 옮기고 temp를 answer에 더해준 후 각 괄호가 가지는 상수값만큼 temp를 나눠준다.

 

그러나 바로 뒤에 여는 괄호가 없을 경우는 이미 위의 상황에서 계산을 해주었기 때문에 각 괄호가 가지는 상수값만큼 temp를 나눠주는 작업만 진행한다.

 

코드

#include<iostream> 
#include<stack>
#include<string.h>

using namespace std;
int main()
{
	stack<char> s;
	string str;
	int answer = 0, temp = 1;
	cin >> str;
    
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] == '(') //일단 시작괄호는 무조건 2를 곱함
		{
			temp *= 2;
			s.push('(');
		}
		else if (str[i] == '[') //일단 시작괄호는 무조건 3을 곱함
		{
			temp *= 3;
			s.push('[');
		}
		else if (str[i] == ')')
		{
			//잘못된 괄호 맺음인 경우
			if (s.empty() || s.top() != '(')
			{
				answer = 0;
				break;
			}
			if (str[i - 1] == '(')
			{
				answer += temp;
			}
			temp /= 2;
			s.pop();
		}
		else if (str[i] == ']')
		{
			if (s.empty() || s.top() != '[')
			{
				//잘못된 괄호 맺음인 경우
				answer = 0;
				break;
			}
			if (str[i - 1] == '[')
			{
				answer += temp;
			}
			temp /= 3;
			s.pop();
		}
	}
	if (!s.empty())
	{
		answer = 0;
	}
	std::cout << answer;
}

여담

예전에 풀었던 문제를 정리하였다. 여러 조건들이 있어 헷갈리기 때문에 문제를 잘 읽고, 올바르게 해석하는 것이 중요한 것 같다. 그리고 우선 효율적인 방법을 고민하되, 너무 고민만 하지 말고 일단 질러서 삽질을 하는 것도 실력향상에 도움이 된다는 것을 느꼈다.