#2504. 괄호의 값
백준사이트의 실버1티어 문제이다. 스택을 활용하는 문제이다.
📖Problems
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
2
Input: (()[[]])([])
Output: 28
예제 2
1
2
Input: [][]((])
Output: 0
🧐Institution
이제 괄호 문제(짝을 맞춰야 하는 문제)하면 스택을 사용해야 한다는것이 거의 공식화되었다.
이 문제도 스택을 활용해서 푼다.
🔍Approach
1. 가능한 조건문 나열하기
조건을 먼저 생각해보자
[→ append(→ append]- stack이 비어있지 않고, 직전에 짝이 있다면 → stack.pop(), 계산 sum = sum * 3
- stack이 비어 있지 않고
stack[-1]==(이라면 → sum = 0, break - stack이 비어있다면 → false
)- stack이 비어있지 않고, 직전에 짝이 있다면 → stack.pop(), 계산 sum = sum * 2
- stack이 비어 있지 않고
stack[-1]==(이라면 → sum = 0, break - stack이 비어있다면 → false
- 이전의 경험을 토대로 닫힌 괄호(
),])가 나오면 stack에 있는 값들을 pop하고, sum에 더하는 것까지는 생각을 했다. - 하지만 그렇게 되면 2를 곱하고 3을 곱하는 각각의 계산과정이 까다로워졌다. 혼자서 40분까지 고민하다가 결국에는 다른 블로그를 보게 되었다.
2. temp 활용하기
( ( ) [ [ ] ] ) = ( 2 + [ 3 ] ) = ( 2 + 3 * 3 ) = (11) = 22
( ( ) [ [ ] ] ) = 2 * ( 2 + 3 * 3 )으로 볼 수 있다.
분배법칙으로 적용해보면 ( 2 * 2 ) + ( 2 * 3 * 3 ) 으로 볼 수 있다.
( ( ) [ [ ] ] ) : tmp = 2, sum = 0
( ( ) [ [ ] ] ) : tmp = 2 * 2, sum = 0
( ( ) [ [ ] ] ) : tmp = 2 * 2 // 2, sum = 2 * 2
( ( ) [ [ ] ] ) : tmp = 2 * 3, sum = 2 * 2
( ( ) [ [ ] ] ) : tmp = 2 * 3 * 3, sum = 2 * 2
( ( ) [ [ ] ] ) : tmp = 2 * 3 * 3 // 3, sum = (2 * 2) + (2 * 3 * 3)
( ( ) [ [ ] ] ) : tmp = 2 * 3 // 3, sum = (2 * 2) + (2 * 3 * 3)
( ( ) [ [ ] ] ) : tmp = 2 // 2, sum= (2 * 2) + (2 * 3 * 3) = 22
🚩Try 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
brackets = input()
stack = []
sum, temp = 0, 1
for i in brackets:
if i == '(' or i == '[':
stack.append(i)
if i == '(' :
temp *= 2
else:
temp *= 3
else:
if i == ')' :
if stack and stack[-1] == '(':
sum += temp
temp = temp // 2
stack.pop()
else:
sum = 0
break
elif i == ']':
if stack and stack[-1] == '[':
sum += temp
temp = temp // 3
stack.pop()
else:
sum = 0
break
print(sum)
Input : (()[[]])
Output : 30
→ Wrong answer. output은 22가 나와야 함. 손으로 flow를 따라가다보면 30이 나올수밖에 없음
temp를 나눠주면서 sum도 더해주기 때문임. sum+=temp와 temp//n부분을 분리해야 함
또 다른 문제도 있다. 마지막에 stack에 값이 남아있는 경우에도 짝이 맞지 않는 것이기 때문에 0으로 출력해주어야 한다.
1
2
3
4
if stack:
print(0)
else:
print(sum)
- 분리를 어떻게 할까 고민하면서 몇 십 번 같은 그림을 또 그리고 손으로 flow 따라가보고 해도 찾을 수 없었다. 그러다가 갑자기 발견했다.
- ( ( ) [ [ ]
])에서 현재 코드 표시된 부분을 보자- 해당 부분에서의 stack = [ ‘(’, ‘[’, ‘[’ ]으로 당연히 코드 상으로 가장 마지막에 있는 것은 열린괄호이다.
- 하지만 내가 구현하고 싶었던 것은 가장 마지막이 아니라 해당 i의 직전노드가 열린괄호일 때이다. 따라서 stack에서 아무리 꺼내와봤자 원하는대로 안 되는 게 당연했다.
- i-1번째것을 가져오기 위해서 input을 list형으로 바꾸어주었고 string형으로 받아주었던 것을 list형으로 바꾸어주었다.
3. flow
이를 통해서 다시 조건을 수정하여 이를 flow에 반영했다. 수정된 flow이다.
- 입력받은 괄호열은
brackets에 list형태로 저장한다.(과[이 각각 다른 값을 가지고 있으므로 해당 여는 괄호가 들어왔을 때 값을 잠시 저장해둘temp변수를 1로 초기화한다. (곱셈을 수행해야 하므로. 최종 답으로 제출할answer변수는 0으로 초기화한다. ‘
(’가 들어왔을 때→ temp에 2를 곱하고 stack에 ‘
(’를 append- ‘
)’가 들어왔을 때- stack이 비어있거나 스택 top이 ‘
(’가 아닌 경우 → 올바르지 않은 괄호열이기 때문에answer = 0,break - 이전 문자열이 ‘
(’일 경우 → 괄호 값이( )이므로temp값을answer에 더해주고,temp를 2로 나눈다. 이후stack에 있는 최상단 값(=’(’)을 pop한다. →answer += temp,temp /= 2,stack.pop() - 이전 문자열이 ‘
(’가 아닐 경우 → 제일 안쪽 괄호 즉, ‘()’ 형태가 아니므로 이미answer에 값이 더해져있는 상태이다. 따라서answer에 값을 더하지 않고temp를 2로 나누고 스택을 pop한다. →temp /= 2,stack.pop()
- stack이 비어있거나 스택 top이 ‘
- ‘
[’ 가 들어왔을 때 (2번과 유사함) temp에 3을 곱하고 stack에 ‘[’를 append - ‘
]’가 들어왔을 때 (3번과 유사함)- stack이 비어있거나 stack top이 ‘
[’이 아닌 경우 → 올바르지 않은 괄호열이기 때문에answer = 0,break - 이전 문자열이 ‘
[’일 경우 →answer += temp,temp /= 2,stack.pop() - 이전 문자열이 ‘
[’이 아닐 경우 →temp /= 2,stack.pop()
- stack이 비어있거나 stack top이 ‘
- 2~6번의 과정을 list의 길이만큼 반복하여 list의 요소들을 다 확인한다.
- 문자열을 다 읽은 후, stack이 비어있지 않을 경우 → 짝이 맞지 않는 괄호열이기 때문에
answer = 0 - stack이 비어있다면
answer를 그대로 출력한다.
🚩My submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
brackets = list(input())
stack = []
answer, temp = 0, 1
for i in range(len(brackets)):
if brackets[i] == '(':
stack.append(brackets[i])
temp *= 2
elif brackets[i] == '[':
stack.append(brackets[i])
temp *= 3
elif brackets[i] == ')' :
if not stack or stack[-1] != '(':
answer = 0
break
if brackets[i-1] == '(':
answer += temp
stack.pop()
temp = temp // 2
else:
if not stack or stack[-1] != '[':
answer = 0
break
if brackets[i-1] == '[':
answer += temp
stack.pop()
temp = temp // 3
if stack:
print(0)
else:
print(answer)
extra) 딕셔너리 이용 (JB선배)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
s = input()
dict = {']':'[', ')':'(', '(':2, '[':3}
stack = []
answer1 = 1
answer2 = 0
for i, c in enumerate(s):
print(answer1, answer2)
if c == '(' or c == '[':
stack.append(c)
answer1 *= dict[c]
elif c == ')' or c == ']':
if not stack:
print(0)
break
elif stack[-1] == dict[c] : # 짝이 맞다면
if dict[c] == s[i-1]:
answer2 += int(answer1)
value = stack.pop()
answer1 /= dict[value]
if len(stack):
print(0)
else:
print(answer2)
- 같은 형식이지만 일일이 2나 3으로 써주지 않고 딕셔너리에 저장하는 방식으로 해도 된다.
- 딕셔너리로 어떻게 하지 어렵고 막막했는데 선배가 딕셔너리로 짜셔서 참고용으로 가져왔다.
💡Retrospect ; 회고
- 처음에 딕셔너리로 짝을 짓는 것도 생각을 했는데, 그렇게 되면 2를 곱하거나 3을 곱하는 과정이 까다로워졌다. 혹시나 다른 분들이 구현했을까 싶어 블로그를 뒤졌지만, 다 똑같은 알고리즘이었다. 나도 결국 그 알고리즘을 참고해 풀었지만, 조금 아쉽다.
- 이전 괄호문제에서 확장성을 갖기위해 선택한 문제였으며 그 목적에 부합했던 것 같다. 이전에 알던 대로만 접근하려고 하니까 숫자를 경우별로 나누는 것이 쉽지 않았다.
- 그래서 비슷한 유형이더라도 참고만 하되 그대로 따라하려는 습관은 고쳐야 할 것 같다.