(알고리즘) 백준 2504 python 파이썬

원종식·2022년 7월 5일

문제

백준 2504 괄호의 값 : https://www.acmicpc.net/problem/2504

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

[][]((])

예제출력2

문제풀이

해당 문제는 stack을 활용해서 풀 수 있는 문제이다.
stack을 활용한다는 의미는 값들을 후입선출 하면서 풀 수 있다는 의미이다.
해당 괄호들이 올바른 괄호열이기 위한 조건들이 있다.
닫는 괄호에서 가장 가까운 여는 괄호는 무조건 같은 쌍이여야 한다. 닫는 괄호를 만났을 때 가장 가까운 여는 괄호가 무엇인지 체크하면서 값을 계산한다.
이를 위해 여는 괄호를 만나면 stack구조에 넣어주고 닫는 괄호를 만나면 가장 위에 있는 괄호가 쌍이 맞을 경우 여는 괄호를 pop해주면 된다.
이를 통해 해당 문자열이 맞는지 아닌지 구분 할 수 있다.
이때 유의사항으로 여는 괄호가 더 많아서 계산하지 못 할 경우가 생기니 이는 마지막에 체크해둔다.
자세한 사항은 코드를 보며 이해해보자

from collections import deque
get=input()
st=deque()#해당 인풋이 정상인지 확인하기 위한 변수
cal=deque()#인풋 계산을 위한 변수
for i in range(0,len(get)):
    if(get[i]=='['):#st와 cal에 값을 넣어준다
        st.append(get[i])
        cal.append(get[i])
    if(get[i]=='('):#st와 cal에 값을 넣어준다
        st.append(get[i])
        cal.append(get[i])
    if(get[i]==')'):#계산이 일어나야 하는 부분
        if(len(st)==0):#만약 이전에 입력된 값이 없으면
            print(0)#에러처리
            exit()#종료
        if(st[-1]=='('):#직전의 괄호가 짝이 맞는 다면
            st.pop()#해당 괄호 세트는 정상이니 pop
            t=[]#계산을 위해 필요한 저장소
            while(cal[-1]!='('):#이전 짝을 찾기 전까지
                t.append(cal[-1])#안에 있는 수 들을 계산을 위한 저장소에 넣는다
                cal.pop()#해당 수를 cal에서 pop
            cal.pop()#마지막 '('까지 pop
            if(len(t)==0):#만약 괄호 안에 계산할 값이 없으면
                cal.append(2)#2를 넣어준다
            else:#있으면
                cal.append(sum(t)*2)#안에 숫자들을 더한뒤 2를 곱한다
        else:#직전의 괄호가 짝이 안맞으면
            print(0)#오류출력
            exit()#종료
    if(get[i]==']'):#위와 똑같이 동작하나 숫자가 3이 됨
        if(len(st)==0):
            print(0)
            exit()
        if(st[-1]=='['):
            st.pop()
            t=[]
            while(cal[-1]!='['):
                t.append(cal[-1])
                cal.pop()
            cal.pop()
            if(len(t)==0):
                cal.append(3)
            else:
                cal.append(sum(t)*3)

        else:
            print(0)
            exit()
if(len(st)!=0):#만약 )]가 없이 ([가 있는 채로 위 반복문을 빠져 나오면
    print(0)#오류출력
    exit()#종료
print(sum(cal))#cal에 남아있는 숫자를 더하면 정답