[백준][파이썬] 16637번 괄호 추가하기

[백준][파이썬]

문제 번호 : 16637
문제 출처 : https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

---

---

Code

from itertools import combinations


def disable(tu):    # 괄호를 둘 수 있는가 판별
    if len(tu) > 1:
        tmp_li = list(combinations(tu, 2))

        for tmp in tmp_li:  # 2개를 골라와서 그 차이가 1이면 괄호를 둘 수 없다.
            if max(tmp) < min(tmp) + 2:
                return True

        return False

    else:
        return False


def calc(expr):
    result = 0
    old_op_idx = -1
    old_op = '+'
    op1 = 0
    for i in range(len(expr)):
        if expr[i] == '+' or expr[i] == '*' 
                or expr[i] == '-' and i - old_op_idx != 1:
            op1 = result
            op2 = expr[old_op_idx+1:i]
            result = eval(str(result) + old_op + expr[old_op_idx+1:i])
            old_op = expr[i]
            old_op_idx = i
    result = eval(str(result) + old_op + expr[old_op_idx+1:])
    return result


n = int(input())
expression = input()    # 수식 입력
num_op = n//2           # 연산자 개수 = 수식 길이 // 2
answer = - 2**31        # -2**31 < ANSWER < 2**31
maximum = 2**31

if n == 1:      # 길이가 1 ==> 숫자 하나 입력
    print(int(expression))
elif n == 3:    # 길이가 3 ==> 연산자 하나를 가지는 수식 입력
    print(eval(expression))
else:
    for br in range(1, num_op//2+1):    # br : 괄호 갯수, 괄호의 최대 개수는 연산자 수 // 2
        cases = list(combinations(range(num_op), br))   # 괄호 br 개를 넣을 수 있는 경우의 수를 모두 찾아냄
        for case in cases:
            if disable(case):   # 괄호를 넣을 수 있는지 판별
                continue
            else:
                ex = expression # 수식을 잠깐 저장
                for i in range(len(case)-1, -1, -1):                # 수식을 뒤에서 부터 수정
                    i = case[i]                                     # 앞에서부터 수정하면 뒷 부분의 index값이 변함
                    ex_li = list(ex) # 수식의 중간을 수정하기 위해 list 형으로 잠시 변환
                    ex_li[i*2: i*2+3] = str(eval(ex[i*2:i*2+3]))    # 수식의 중간 부분 수정
                    ex = ''.join(ex_li)                             # join()함수로 list를 다시 str으로 변환
                answer = min(max(calc(ex), answer), maximum)        # 계산 결과와 원래 값 중 최대값을 비교
                                                                    # 문제에서의 최대값을 넘어가지 않도록 비교
    print(answer)

Idea

1. 입력 예시 1을 기준으로 설명하겠다. 재귀 함수를 사용하면 더 쉬울 듯 하다.
   예를 들어 3+8*7-9*2 가 입력되면 3+8을 한 후 7-9*2를 재귀함수의 입력으로 넣고 다시 2를 입력으로 넣는 방식으로 풀어도 괜찮을 듯 한데 재귀함수를 많이 접하지 않아서 만들지 못했다.
2. 그래서 단순 반복으로 했는데 괄호가 들어갈 수 있는 위치의 모든 경우의 수를 구해야 했다. 우선 괄호의 최대 개수는 입력된 수식에서 연산자 개수를 2로 나눈 몫이다.
3. 괄호가 1개인 경우부터 최대 개수까지 반복해서 연산자의 개수에서 괄호 개수 만큼 가능한 모든 조합을 뽑아서 조건을 확인한다. 괄호 연산이 가능한 조건은 한 가지 뿐이다. 괄호 연산을 할 연산자가 붙어 있으면 안 된다.
4. 괄호 계산을 먼저 한 후 문자열에서 3글자를 한 숫자로 바꾸어주어야 했는데 str 형에서 문자를 대체하는 replace()함수로 구현을 하게 되면 바꾸려는 문자열과 같은 문자열이 더 앞에 존재하면 원하는 위치가 아니라 엉뚱한 문자열을 바꾼다.
   ex) 예제 입력 6에서 수식은 1-9-1-9-1-9-1-9-1-9 일 때
   1-9-1-9-(1-9)-1-9-1-9, 1-9-1-9-1-9-1-9-(1-9) 두 경우 모두 -8-1-9-1-9-1-9-1-9로 바뀐다.
   그래서 문자열로 표현된 수식을 잠깐 리스트로 바꿔서 원하는 위치의 문자들을 바꾼후 다시 str로 변환한다. 문자열로 바꿀 때는 전에 사용했던 ''.join()을 사용했다.
   ( 문자열은 튜플 같이 요소들의 직접적인 변경이 허용되지 않는다. ex) str[0] = 'a' error
5. 수식을 계산하는 함수 calc()를 살펴보면 연산자의 위치를 찾고 연산자가 나타날 때까지의 수를 operand로 사용해서 그 전의 값과 old_op에 해당하는 연산을 수행한다. 만약 연산자 뒤에 바로 -가 나오면 그건 음수를 뜻하는 것으로 if 문에서 False가 되어 동작하지 않는다.
6. 수식의 길이가 1인 경우와 3인 경우에는 괄호의 최대 개수가 0으로 되어 동작하지 않아서 처음에 예외 처리를 해두었다.

이번 코드는 재귀함수로 여러 번 시도하다가 안 돼서 시간이 오래 걸렸다. 이 문제에서 처음으로 사용한 함수는 eval()이라는 함수이다. 어떤 책에서는 괄호 안의 수식을 계산해주는 함수라고만 설명이 되어 있다. 하지만 eval()은 괄호 안에 파이썬 명령어를 써 넣으면 명령어에 해당하는 동작을 수행하고 그 값을 반환해준다.

s = "\"Hello World\""
eval("print(" + s + ")")

# 결과
# Hello World

내가 봐도 코드가 이해가 안 될 수 있는 부분들이 많아서 설명이 길어졌다. 더 클린한 코드를 짜도록 노력해야겠다.