알고리즘: 백준 14888번 연산자 끼워넣기(feat. python)

백준 14888번 링크입니다. 

14888번: 연산자 끼워넣기

 

 

이렇게 열심히 풀긴 했지만 결국 틀렸다...

 

하지만 이 문제 하나로 여러가지 경험을 한 것 같아서 만족한다. 

 

permutation이라는 편리한 모듈을 알게 되었고

 

stack과 dfs에 대해서 좀 더 깊게 알 수 있었다. 

 

permutation을 통해서 가능한 연산자순서의 경우의 수를 구했고

 

stack을 통해 필요한 값을 넣고 뺌으로써 원하는 값을 구하는 방법을 체득하였다. 

 

 

import sys
from itertools import permutations

input = sys.stdin.readline 


N = int(input())
number_list = list(map(int, input().split()))
get_operator = list(map(int, input().split()))
dic = {0: "+", 1: "-", 2: "*", 3:"//"}
operation_tmp = []
sum_list = []
stack = []


for i in range(4):
    for j in range(get_operator[i]):
        operation_tmp.append(dic[i])
        
operation_list = set(permutations(operation_tmp, N - 1))


for operation in operation_list:

    tmp = str(number_list[0])
    stack.append(tmp)
    
    for i in range(N - 1):
        stack.append(operation[i])
        stack.append(str(number_list[i + 1]))

        if operation[i] == "//":
     
            if int(stack[0]) < 0 and int(stack[2]) > 0:
                stack[0] = str(-int(stack[0]))
                
            elif int(stack[0]) > 0 and int(stack[2]) <0:
                stack[2] = str(-int(stack[2]))

        if len(stack) == 3:
            tmp = (eval("".join(stack)))
            stack = [str(tmp)]
            
        if i == N - 2:
            sum_list.append(int(tmp))
            stack = []


print(max(sum_list))
print(min(sum_list))