[알고리즘/자료구조] 2504번 : 괄호의 값 - python
링크 : https://www.acmicpc.net/problem/2504
2504번: 괄호의 값
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X
www.acmicpc.net
- 문제
- 소요시간: 22분, 실패
- 설계하기(접근방법)
1. 문자열을 입력받는다, 스택을 선언한다
2. 알고리즘 해석
1) 만약 괄호가 열리면, stack에 append하고 괄호 내의 숫자는 후에 2or 3만큼 곱해진다
따라서 tmp 를 선언하여 그 변수를 제어해준다.
2) 괄호가 닫히고, 그 직전 괄호가 그 괄호의 쌍'()' or '[]' 이였다면 지금까지 곱해진 tmp만큼 ans에 더해줌그리고 stackpop()
또한 괄호가 닫히면 지금까지 곱해진 숫자를 ']' ,')'를 tmp에서 나누어준다.
3) 만약 괄호가 닫힐 때, 스택 가장 위에 있는 원소가 쌍이 안맞으면, 잘못된 괄호식이니 ans = 0 으로 해주고 break 해준다
예제를 해석하면
( ( ) [ [ ] ] ) ( [ ] )
( -> stack에 append, tmp * 2 현재 tmp = 2
( -> stack에 append, tmp * 2 현재 tmp = 4
) -> 직전의 stack[-1] 이 ')'이니 ans += tmp, tmp //= 2 -> 현재 tmp = 2, ans = 4
[ -> stack에 append, tmp * 3 현재 tmp = 6
[ -> stack에 append, tmp * 3 현재 tmp = 18
] -> 직전의 stack[-1] 이 ']'이니 ans += tmp, tmp //= 3 -> 현재 tmp = 6, ans = 22
] -> 직전의 stack[-1] ']'가 아님 tmp //= 3 만 진행 현재 tmp = 2,
) -> 직전의 stack[-1] ')'가 아님 tmp //= 2 만 진행 현재 tmp = 1,
( -> stack에 append, tmp * 2 현재 tmp = 2
[ -> stack에 append, tmp * 3 현재 tmp = 6
] -> 직전의 stack[-1] 이 ']'이니 ans += tmp, tmp //= 3 -> 현재 tmp = 2, ans = 28
] -> 직전의 stack[-1] ']'가 아님 tmp //= 3 만 진행 현재 tmp = 1,
ans = 28
- 코드(출력)
stack = []
n = list(input())
ans = 0
tmp = 1
for i in range(len(n)): # (()[[]])([])
if n[i] == '(':
stack.append(n[i])
tmp *= 2
elif n[i] == '[':
stack.append(n[i])
tmp *= 3
elif n[i] == ')':
if not stack or stack[-1] == '[':
ans = 0
break
if n[i-1] == '(':
ans += tmp
tmp //= 2
stack.pop()
elif n[i] == ']':
if not stack or stack[-1] == '(':
ans = 0
break
if n[i-1] == '[':
ans += tmp
tmp //= 3
stack.pop()
if stack:
print(0)
else:
print(ans)- 얻어갈 부분
1. 스택 자료구조를 사용할 때, 스택 하나로만 제어하려고 하지 말고, 필요하다면 추가적인 리스트나 변수를 선언하여 흐름을 제어해야 할 것이다.