[BOJ / 백준] 16637번 괄호 추가하기 파이썬(Python) 문제 풀이

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

 

 

 

 

CODE

import sys

input = sys.stdin.readline

result = -2 ** 31 - 1   # 최솟값 -1


def calc(num, op):      # 남은 수식을 전부 계산하는 함수
    while op:
        oper = op.pop(0)
        n1, n2 = num.pop(0), num.pop(0)
        if oper == '+':
            num.insert(0, n1 + n2)
        elif oper == '-':
            num.insert(0, n1 - n2)
        elif oper == '*':
            num.insert(0, n1 * n2)
    return num[0]


def solve(cnt, num, op):
    global result
    if cnt == n // 2 or len(num) == 1:      # 수식의 끝까지 도달했거나 남은 피연산자가 1개인 경우 종료
        result = max(result, calc(num, op))
        return

    solve(cnt + 1, num[:], op[:])           # 이번 연산자를 우선 계산하지 않고 넘김

    try:
        n1, n2 = num.pop(cnt), num.pop(cnt) # 괄호를 추가한 경우
        oper = op.pop(cnt)                  # 우선적으로 계산한다
        if oper == '+':                     # 이 연산자 바로 다음 연산자는 우선 계산하지 않는다(괄호 중첩)
            num.insert(cnt, n1 + n2)
        elif oper == '-':
            num.insert(cnt, n1 - n2)
        elif oper == '*':
            num.insert(cnt, n1 * n2) 
                                            # pop, insert 연산으로 index가 1감소했기 때문에
        solve(cnt + 1, num[:], op[:])       # 바로 다음 연산자를 건너뛰지만, cnt를 1만 증가시킨다
                                             
    except:
        0           # 남은 연산의 수가 없는 경우 pop에서 index range error 발생


n = int(input())
expr = input()
num, op = [], []
for i in range(n):  # 연산자와 피연산자를 나누어 저장
    if i % 2 == 0:
        num.append(int(expr[i]))
    else:
        op.append(expr[i])
solve(0, num, op)
print(result)

 

 

 

 

 

풀이

💡 idea

어려웠샤...😢

- 연산자와 피연산자를 나누어 저장한다 (남은 개수 파악과 연산에 용이)

- 괄호는 연산자를 기준으로 선택한다

- i번 연산자를 괄호 추가했다면 i+1번 연산자에는 괄호를 추가할 수 없다 (괄호 중첩)

- 종료 조건

    ˙ 피연산자가 하나만 남은 경우

    ˙ 마지막 연산자까지 선택이 끝난 경우

 

 

💡 implementation

num, op = [], []
for i in range(n):
    if i % 2 == 0:
        num.append(int(expr[i]))
    else:
        op.append(expr[i])

- 리스트 num에 피연산자, op에 연산자 저장

 

solve(cnt + 1, num[:], op[:])

- 리스트를 넘길 때는 [:]으로 복사해서 넘겼다

- deepcopy()는 다중리스트를 깊은 복사할 때는 유용하지만, 일차원 리스트를 깊은 복사하는 경우에는 list_name[:]을 사용하는 것이 시간이 훨씬 짧다!

 

try:
    n1, n2 = num.pop(cnt), num.pop(cnt)
    oper = op.pop(cnt)   
    if oper == '+':
        num.insert(cnt, n1 + n2)
    elif oper == '-':
        num.insert(cnt, n1 - n2)
    elif oper == '*':
        num.insert(cnt, n1 * n2)

    solve(cnt + 1, num[:], op[:])

except:
    0

- pop()에서 out of index error 가 발생한 경우 연산을 건너뛰기 위해 try-except문 사용

- 종료 조건을 더 잘 설정했더라면 피연산자와 연산자 수가 부족할 때 이 구문까지 오지 않았겠지만 이렇게 해도 정답이라구요 🙄

 

 

 

 

 

결과

어려웠어요.. 괄호 중첩 고려하는데 시간이 좀 걸려서 😵

하지만 해냈닷 😎