[백준 2504] 괄호의 값

괄호의 값(2504)

이 문제는 2008년 정보 올림피아드 지역 본선 초등부 4번, 중등부 2번 문제 입니다.

문제 이해하기

괄호 관련 문제가 보인다면 먼저 스택이 아닌가 생각해 보아야 합니다. 괄호 관련 문제는 스택의 특성을 이용해서 해결하는 경우가 많기 때문 입니다. 괄호 문제를 푸는 방법에 대해서는 아래 링크에서 소개 했었습니다. 아래 링크를 통해 괄호 문제를 어떻게 바라봐야 하는지 확인 바랍니다.

https://davincicoding.tistory.com/189

[백준 9012] 괄호

 

이 문제에서는 괄호가 한 가지가 아니라 두 가지 입니다. 그 두 괄호가 올바른 괄호인지 파악해야 합니다. 그리고 괄호를 통해 곱하기, 더하기 연산을 진행해야 합니다. 복잡하기 때문에 하나하나 해결해 보겠습니다.

올바른 괄호 확인

올바른 괄호인지 아닌지를 판단하는 것은 위 괄호 문제와 같은 방법으로 진행 합니다. 다만 괄호가 두 가지가 있기 때문에 각각의 괄호를 따로 진행 합니다. ‘ ( ’ , ‘ [ ’ 와 같이 열리는 괄호는 숫자를 늘려나가고, ‘ ) ‘, ‘ ] ‘ 와 같이 닫히는 괄호를 만나면 숫자를 줄여나갑니다. 괄호의 숫자 계산 결과가 음수가 나온다면 닫힌 괄호가 더 많아 올바른 괄호가 아니기 때문에 로직을 중지하고 0을 출력합니다. 또는 모든 계산이 끝났을 때 숫자가 0이 아니라면 열린 괄호가 많다는 뜻이기 때문에 올바른 괄호가 될 수 없습니다. 이 때 역시 0을 출력하고 종료합니다.

점수 계산

점수를 계산하는 방법은 닫힌 괄호를 만났을 때 시작됩니다. 전체의 괄호 ‘ ( ) ‘나 ‘ [ ]’를 만나면 2, 3으로 변경하여 저장합니다. 그리고 닫힌 괄호인 ‘ ) ‘ 나 ‘ ] ‘를 만나게 된다면 저장된 숫자를 모두 더한 다음에 2나 3을 곱해 줍니다. 문제에 주어진 방법 그대로 풀이한 것입니다.

분배 법칙 풀이

다른 사람들이 작성한 내용을 보니 분배 법칙을 사용해서 푸는 것이 많이 보였습니다. 문제를 풀었을 때는 이 방법이 생각이 나지 않았는데 다른 사람들의 풀이를 보니 분배 법칙을 이용하는 것이 더 좋은 방법으로 보였습니다. 분배 법칙이 바로 생각나면 좋겠지만 보통 미리 준비하지 않으면 생각나지 않는 방법이라 생각합니다. 분배 법칙의 방법도 나중에 작성해 보겠습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력과 출력

arr = input()
print(solve(arr))

문자열 arr을 입력 받습니다. solve 함수를 통해 문제를 해결하고 그 결과를 출력합니다.

solve 함수 - 올바른 괄호 확인

def solve(arr):
    cnt = [0, 0]
    for a in arr:
        if a == '(': 
            cnt[0] += 1
        elif a == '[':
            cnt[1] += 1
        else:           
            if a == ')':
                cnt[0] -= 1
            elif a == ']':
                cnt[1] -= 1
            
            if cnt[0] < 0 or cnt[1] < 0:
                return 0
            
    if sum(cnt):
        return 0

괄호가 두 종류가 있기 때문에 () 괄호는 cnt의 0번째 인덱스에, [] 괄호는 cnt의 1번째 인덱스에 저장합니다. 두 괄호의 계산 결과가 0보다 작아지면 바로 0을 리턴합니다. 또 모든 계산을 마치고 cnt에 남아있는 숫자가 있다면 0을 리턴합니다

solve 함수 - 점수 계산

위 로직에 추가되는 부분이 많습니다. 어디가 추가 되었는지 잘 확인해 보시기 바랍니다.

def solve(arr):
    st = []
    cnt = [0, 0]
    for a in arr:
        if a == '(': 
            st.append(a)
            cnt[0] += 1
        elif a == '[':
            st.append(a)
            cnt[1] += 1
        else:
            if not st:
                return 0
            
            top = st.pop()
            value = 0
            if a == ')':
                cnt[0] -= 1
                value = 2
                if top == '(':
                    st.append(value)
            elif a == ']':
                cnt[1] -= 1
                value = 3
                if top == '[':
                    st.append(value)
            
            if cnt[0] < 0 or cnt[1] < 0:
                return 0
            
            if value:
                temp = 0
                while isinstance(top, int):
                    temp += top
                    top = st.pop()
                temp *= value
                st.append(temp)

    if sum(cnt):
        return 0

    return sum(st)

st라는 스택을 추가했습니다. st에는 열린 괄호와 숫자들이 들어갑니다. 닫히는 괄호를 만날 때 연산이 시작 됩니다. 기존에 스택에 들어 있는 괄호를 확인해서 ‘ ( ) ’ 를 만나면 2를 넣어주고, ‘ [ ] ‘를 만나면 3을 넣어줍니다. 그냥 닫히는 괄호인 ‘ ) ‘ 나 ‘ ] ‘를 만나면 저장된 숫자들을 모두 더해준 뒤 괄호의 값을 곱합니다. 최종적으로 st에 저장된 값을 모두 더하여 출력하면 됩니다.