[백준] 2504번: 괄호의 값 - Python

링크: https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

---

---

 

풀이

+기를 기준으로 리스트를 나눠서 계산해보면 쉽게 풀리지 않을까?

• 스택을 이용해 문자열을 돌며 올바르게 입력된 괄호인지 판단하자
• 돌다가 스택의 크기가 0되기 전에는 곱하기
• 0이 되면 곱한 것들을 따로 result와 더하고 result에 저장
• 다시 계속 반복
• 모든 문자열을 돌았으면 result가 답?

위의 구조로 코드를 짜봄

import sys
input = sys.stdin.readline

brackets = input()

st = []
st.append(brackets[0])

tmp = 1
result = 0

for i in range(1, len(brackets)):
    # 올바르지 않은 입력일 시 0 출력
    if (brackets[i] == ')' and (len(st)==0 or st[-1] != '(')) or (brackets[i] == ']' and (len(st)==0 or st[-1] != '[')):
        print(0)
        exit()
    # flag는 닫혔다는걸 표시
    elif brackets[i] == ')':
        st.pop()
        tmp *= 2
    elif brackets[i] == ']':
        st.pop()
        tmp *= 3
    else:
        st.append(brackets[i])
    # st의 크기가 0이 되면 따로 빼주고 더해줘야함
    if len(st) == 0:
        result+= tmp
        tmp = 1

print(result)

하지만 답이 나오지 않음

스택의 크기가 0이 되기 전에는 계속 곱 연산이 되는 것이 아니라 그 안에서도 +연산이 존재 할 수 있음

그럼 위 코드를 함수로 만들어 재귀호출을 하는 식으로 하면 안될까?

음 뭔가 될거 같은데 중간에 막히는 느낌이다. 

 

인터넷에 풀이를 찾아본 결과 분배법칙을 적용하여 풀어야 한다고 한다...

 

( ( ) [ [ ] ] )의 형태는 2*(2+3*(3))으로 계산이 되는데

이를 분배 법칙을 이용하면 (2*2) + (2*3*(3)) 이 된다.

이 부분을 어떻게 코드로 적용을 시키냐 변수 두 개를 활용하면 된다.

'( ( ) [ [ ] ] )' : tmp = 2, ans = 0

'( ( ) [ [ ] ] )' : tmp = 2 * 2, ans = 0

'( ( ) [ [ ] ] )' : tmp = 2, ans = 2 * 2     (ans값에 더하기)

'( ( ) [ [ ] ] )' : tmp = 2 * 3, ans = 2 * 2

'( ( ) [ [ ] ] )' : tmp = 2 * 3 * 3, ans = 2 * 2

'( ( ) [ [ ] ] )' : tmp = 2 * 3, ans = (2 * 2) + (2 * 3 * 3)     (ans값에 더하기)

'( ( ) [ [ ] ] )' : tmp = 2, ans = (2 * 2) + (2 * 3 * 3)

'( ( ) [ [ ] ])' : tmp = 1, ans =(2 * 2) + (2 * 3 * 3)
출처

기본적인 스택을 이용한 올바른 괄호 판별 알고리즘과 유사함

• 여는 괄호가 나오면 tmp에 append를 한다
• 닫는 괄호가 나왔을 때가 나오면 바로 앞에 괄호가 짝이 맞는 괄호인지 확인한다.
• 짝이 맞는 괄호이면 tmp의 값을 ans에 넣어준다.
• 짝이 맞지 않는 괄호이면 그냥 pop을 해준다.

위 조건으로 구현

import sys
input = sys.stdin.readline

brackets = input()

st = []

tmp = 1
ans = 0

for i in range(len(brackets)):
    # 올바르지 않은 입력일 시 0 출력
    if (brackets[i] == ')' and (not st or st[-1] != '(')) or (brackets[i] == ']' and (not st or st[-1] != '[')):
        print(0)
        exit()
    elif brackets[i] == '(':
        st.append(brackets[i])
        tmp *= 2
    elif brackets[i] == '[':
        st.append(brackets[i])
        tmp *= 3
    elif brackets[i] == ')':
        if brackets[i-1] == '(':
            ans += tmp
            tmp //= 2
        else:
            tmp //= 2
        st.pop()
    elif brackets[i] == ']':
        if brackets[i-1] == '[':
            ans += tmp
            tmp //= 3
        else:
            tmp //= 3
        st.pop()

print(ans)

 

 근데 자꾸 44%에서 틀렸다고 나온다.. 왜 그럴까?

 

올바르지 않은 입력을 판별하는 코드가 닫히는 괄호가 나올 때만 판별해서 닫히는 괄호가 부족한 경우에는 인식을 못한다

 

예)  [[] -> 3으로 출력

 

이러한 경우는 홀수인 경우만 나타나기 때문에 위에서 홀수인지 미리 판별을 하면 해결 할 수 있다.

정답코드

import sys
input = sys.stdin.readline

brackets = input()

st = []

tmp = 1
ans = 0

if (len(brackets)-1)%2 !=0:
    print(0)
    exit()

for i in range(len(brackets)):
    # 올바르지 않은 입력일 시 0 출력
    if (brackets[i] == ')' and (not st or st[-1] != '(')) or (brackets[i] == ']' and (not st or st[-1] != '[')):
        print(0)
        exit()
    elif brackets[i] == '(':
        st.append(brackets[i])
        tmp *= 2
    elif brackets[i] == '[':
        st.append(brackets[i])
        tmp *= 3
    elif brackets[i] == ')':
        if brackets[i-1] == '(':
            ans += tmp
            tmp //= 2
        else:
            tmp //= 2
        st.pop()
    elif brackets[i] == ']':
        if brackets[i-1] == '[':
            ans += tmp
            tmp //= 3
        else:
            tmp //= 3
        st.pop()

print(ans)

 

얻어간 부분

• 조건을 판단하는 코드가 모든 상황에서 적용이 되는지 잘 생각하고 코드를 짜야겠다