[백준 / 2504] 괄호의 값

in Problem Solving on BaekJoon


날짜: 2021년 9월 15일
소요 시간: 1시간 22분 25초
카테고리: 자료구조, 구현
태그: silver.2, 2504, 파이썬

백준 2504 - 괄호의 값

입출력 예시

예제 입력예제 출력
(()[[]])([])28
[][]((])0

내가 적은 코드

import sys

str_braket = sys.stdin.readline().strip()
str_braket = str_braket.replace('()','2')
str_braket = str_braket.replace('[]','3')
braket = list()
answer = 0

for j in str_braket:
    braket.append(j)

while len(braket) != 1:
    if braket.count('(') != braket.count(')') or braket.count('[') != braket.count(']'):   # 예외1) 괄호가 제대로 닫히지 않았을 때
        braket = ['0']
        break
    check_braket = braket
    str_stack = list()
    int_stack = list()
    for idx, i in enumerate(check_braket):
        if i == '(':
            str_stack.append(i)
            first_index = idx
        elif i == '[':
            str_stack.append(i)
            second_index = idx
        elif i == ')':
            if len(str_stack) > 0 and str_stack.pop() == '(':
                answer = int_stack.pop() * 2
                braket[first_index:idx+1] = ' '
                braket[first_index] = str(answer)
                break
            else:   # 예외2) str_stack이 비었는데 ')'가 나왔을 경우
                braket = ['0']
                break
        elif i == ']':
            if len(str_stack) > 0 and str_stack.pop() == '[':
                answer = int_stack.pop() * 3
                braket[second_index:idx+1] = ' '
                braket[second_index] = str(answer)
                break
            else:   # 예외3) str_stack이 비었는데 ']'가 나왔을 경우
                braket = ['0']
                break
        else:
            if idx != 0 and check_braket[idx-1] != '(' and check_braket[idx-1] != ')' and check_braket[idx-1] != '[' and check_braket[idx-1] != ']':
                sum_num = str(int(check_braket[idx - 1]) + int(check_braket[idx]))
                braket[idx-1:idx+1] = ' '
                braket[idx-1] = str(sum_num)
                break
            else:
                int_stack.append(int(i))


if braket[0] == ']' or braket[0] == ')' or braket[0] == '[' or braket[0] == '(':   # 예외4) 괄호열의 길이가 1인 경우
    print(0)
else:
    print(int(''.join(braket)))

풀이 과정

  1. 완성되어 있는 ‘()’나 ‘[]’를 2와 3으로 치환
  2. str_braket에 문자열을 배열로 변환
  3. braket의 길이가 1이 될 때까지 반복
    • check_braket에 braket 저장
      • 삭제 및 삽입 연산에 영향을 주지 않기 위한 저장소 생성
    • 문자열과 정수를 임시 저장 할 두개의 stack 생성
    • 예외 처리 1 : (ex. ‘())[]’, ‘(([])’)
      • 괄호의 개수가 홀수개일 때 0을 반환
    • check_braket을 enumerate() 함수를 활용하여 인덱스와 원소만큼 반복
      • ’(‘가 나왔을 때 : str_stack 원소 저장 후 first_index에 인덱스 저장
      • ’[‘가 나왔을 때 : str_stack 원소 저장 후 second_index에 인덱스 저장
      • ’)’가 나왔을 때 : braket 배열의 first_index부터 idx 인덱스까지 삭제 후 answer에 저장되어 있는 정수에 *2해서 저장
      • 예외 처리 2 : (ex. ‘)
        • str_stack이 비었는데 ‘)’가 나왔을 경우 0을 반환
      • ’]’가 나왔을 때 : braket 배열의 second_index부터 idx 인덱스까지 삭제 후 answer에 저장되어 있는 정수에 *3해서 저장
      • 예외 처리 3 : (ex. ‘]
        • str_stack이 비었는데 ‘]’가 나왔을 경우 0을 반환
      • 숫자가 나왔을 때 :
        • 이전 인덱스의 원소가 숫자일 경우 두 숫자를 더함
        • 이전 인덱스의 원소가 숫자가 아닐 경우 int_stack에 숫자 저장
  4. 예외 처리 4 : (ex. ‘(‘, ‘)’, ‘[’, ‘]’)
    • 괄호열의 길이가 1인 경우 0을 출력
    • 아닐 경우 반복문 안에서 계산이 끝난 정수 출력

베스트 코드

def f(p):
    if len(p) == 0 : return 1
    dic = {'(':')', '[':']'}
    ans, sub, stk = 0, '', []
    for i in p:
        sub += i
        if len(stk) > 0 and dic.get(stk[-1], '') == i: stk.pop()
        else : stk.append(i)
        if len(stk) == 0: ans, sub= ans + f(sub[1:-1]) * (2 if sub[0] == '(' else 3), ''
    if len(stk) > 0 : return 0
    return ans

print(f(input()))

반성

  • 모든 경우를 다 처리하게끔 빡구현으로 코드를 짜서 코드가 많이 길고 버그가 날 때마다 그때그때 예외처리를 빼어주다보니 코드가 많이 지저분하다.


© 2021. by hminkim