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

문제

우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.

2. ‘[]’ 인 괄호열의 값은 3이다.

3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.

4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2504)

풀이

처음에 문제를 보고는 생각보다 스택을 써서 풀면 간단하겠다 생각들었지만..! 잘 풀리지 않아 이후에 하드코딩을 했는데도 풀리지 않았습니다. 다시 쉽게 문제를 생각해보려 친구의 힌트를 얻어서(거의 풀이를 해줬지만) 풀었습니다. 스택을 이용해서 풀 수 있는데 () 또는 []가 들어올 경우에는 바로 숫자로 계산할 수 있으니 2 또는 3을 push합니다. (나 [가 들어오더라도 이후 짝을 찾아야 하니 push합니다. )와 ]가 들어왔을 때 처리를 잘해줘야 하는데, 올바른 괄호열이라면 )가 들어왔다면 스택에 분명히 (가 쌓여있을 것 이고 ]가 들어왔다면 스택에 분명히 [가 들어와있을 것입니다.(들어와있지 않다면 올바르지 않으므로 0을 출력하도록 합니다.) 만약 [[][]] 가 들어온다면 맨 마지막 ]가 들어올 때 스택에는 [ 3 3 이 쌓여있을 겁니다. 원하는 결과값은 18일 것입니다. 따라서 스택에 숫자가 있다면 해당 숫자들을 다 더한다음(3+3)*3 을 해주면 원하는 값이 됩니다. )일 경우에는 안의 값을 다 곱하고 *2를 해주면됩니다. 이 때 스택을 char로 선언한다면 (, [는 문제없이 들어가겠지만 숫자가 두자리수부터는 불가능합니다. 어떻게 해결할 수 있을까 생각하다가 (는 -1, [는 -2로 처리해주었습니다. 이렇게 반복적으로 입력받은 문자열에 대한 스택을 쌓아나가면 마지막엔 스택에 숫자들만 남아있을 것이고, 이 숫자들을 다 더한 값이 원하는 최종 결과값이 됩니다. 결국엔 처음에 생각했던 로직과 비슷하게 풀어나간 것 같다는 생각이 들었지만 좀 더 깔끔하게 정리하지 않고 문제를 풀려해서 잘 풀리지 않았던 것 같습니다. 

생각보다 예외가 많은 문제였습니다. ()), (, [ 와 같이 올바른 괄호열이 아닐 경우 0을 출력해주도록 처리해야합니다.

코드

https://github.com/kswim/Algorithm/blob/master/Stack/2504.cpp