문제
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
예제 입력 1
(()[[]])([])
예제 출력 1
28
에제 입력 2
[][]((])
예제 출력 2
0
문제 해결 과정
이 문제는 자료구조를 잘 선택하는 거보다, 괄호에 따라서 어떻게 연산을 해나갈지 잘 구현해야하는지에 따라 문제 해결의 행방이 결정된다 생각하여 구현 문제라고 생각했다.
나는 처음에 괄호들을 list로 담고 pop을 하면서 괄호에 따라서 연산을 진행하려고 했다.
나중에 알고 보니, 그렇게 해도 틀린 방법은 아닐수도 있지만 한 시간 동안 답을 찾지 못해 참고한 블로그에서는 앞에서 부터 for 문을 통해 괄호에 따라 연산을 했다.
과정은 다음과 같다.
현재 예시를 보면 '(()[[]])([])'는 2(2+33)+33'으로 바뀔 수 있다.
그러면 분배 법칙(?)에 의하여 22 + 233 + 3*3 으로 변할 수도 있다.
이 점을 이용한 것 같았다.
일단 '('이 나오면 tmp라는 값에 2를 곱한다. 그리고 ')'이 나오면 이전에 '('이 나왔는지 확인하고 나왔다면 result 값에 현재 tmp 값을 더한 다음에 2로 tmp를 나눈다. '[', ']'도 같은 방식이다.
그리고 '(', '['가 나올 때마다 stack에 담아 둔다.
왜냐하면 다 끝나고도 stack에 남아있다면 닫힌 괄호가 다 나왔음에도 불구하고 남은 것이기 때문에 0을 print 해야 한다.
최종 코드
arr=input()
stack=[]
answer=0
tmp=1
for i in range(len(arr)):
if arr[i] =='(':
stack.append(arr[i])
tmp *=2
elif arr[i] == '[':
stack.append(arr[i])
tmp *=3
elif arr[i] == ")":
if not stack or stack[-1] == "[":
answer = 0 # 실패
break
if arr[i-1] == "(":
answer += tmp
stack.pop()
tmp //= 2 #tmp 초기화
else:
if not stack or stack[-1] == "(":
answer=0
break
if arr[i-1] =='[':
answer+=tmp
stack.pop()
tmp //=3 #tmp 초기화
if stack:
print(0)
else:
print(answer)참고 블로그
