📜 문제 이해하기
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) ()는 2이다.
2) []은 3이다.
3) 숫자가 연속으로 있다면 덧셈을하자 ex) (2 3) -> (5)
4) ()안에 숫자가 있다면 x2를 하자
5) []안에 숫자가 있다면 x3를 하자
✏️ 계획 수립
스택을 사용해서 문제를 풀어보기로해보자.
우선 스택이 2개가 필요하다.
1) 값을 계산하기 위한 스택
2) 괄호의 무결성을 확인하기 위한 스택
위 스택을 가지고 인풋값을 하나하나 살펴보면서 아래 로직대로 진행하면 된다.
(무결성은 수도코드에는 포함하지 않았다.)
1) 만약 n이 )이라면
a) 스택에 숫자가 있다면 숫자가 나오지 않을때까지 더해주고 2를 곱해준 값을 스택에 넣는다.
b) 만약 (라면 2를 스택에 넣어준다.
2) 만약 n이 ]이라면
a) 스택에 숫자가 있다면 숫자가 나오지 않을때까지 더해주고 3를 곱해준 값을 스택에 넣는다.
b) 만약 (라면 3를 스택에 넣어준다.
3) 둘다 아니면 스택에 넣어준다.
💻 계획 수행
def logic(compare, num, _stack):
tmp = 0
while isinstance(stack[-1], int):
tmp += _stack.pop()
if tmp != 0:
_stack.pop()
_stack.append(tmp * num)
if _stack[-1] == compare:
_stack.pop()
_stack.append(num)
if __name__ == '__main__':
stack = []
bracket_stack = []
N = input()
for n in N:
if n == ')':
if bracket_stack and bracket_stack[-1] == '(':
bracket_stack.pop()
logic('(', 2, stack)
else:
print(0)
exit(0)
elif n == ']':
if bracket_stack and bracket_stack[-1] == '[':
bracket_stack.pop()
logic('[', 3, stack)
else:
print(0)
exit(0)
else:
bracket_stack.append(n)
stack.append(n)
if not bracket_stack:
print(sum(stack))
else:
print(0)🤔 회고
스택을 이중으로 사용한게 조금은 아쉽다. 더 공간을 아끼면서 풀 수 있는 방법이 있을 것 같다.
