[백준] 14888번: 연산자 끼워넣기 Python (DFS, BFS) | LIM

이 문제의 경우는 순서대로 연산자에 상관없이 계산해야하기 때문에 연산자를 하나씩 뽑아서 즉, popleft를 사용하여 구현해야 한다고 생각했다. 즉 BFS를 사용하여 문제를 해결하였다.

 

1. 숫자는 순서의 바뀌지 않고 연산자의 순서만 바뀌기 때문에 연산자의 조합이 어떻게 올 지 부터 먼저 구해야 한다.

 (조합은 permutation을 이용하여 구했다. 다만, permutation의 경우 ['+','+','+','+']의 경우 모두 다르게 인식하여 경우의 수를 많이 만들기 때문에 set을 사용하여 조합을 unique한 상태로 변경해야 한다.)

 

2. 연산자의 특성 중 나눗셈 부분이 기존 나눗셈의 개념과는 다르기 때문에 나같은 경우 함수로 사칙연산을 구현해주었다. 
 (생각보다 시간이 오래 걸리지 않았다..)

 

3. 연산자의 조합을 사용하여 구한 값을 answer_list 안에 append시킨 후 제일 큰값(max) 과 제일 작은값(min) 을 뽑아내었다.

 

**처음에 permutation에 set을 안써서 시간초과가 났었다. 유의해야 한다.

 

# 연산자 끼워넣기
from itertools import permutations
from collections import deque
import copy

n = int(input())
number_list = list(map(int,input().split()))
number_origin = copy.deepcopy(number_list)
pl,mi,mu,di = map(int,input().split())

# 사칙 연산의 개수가 주어지기 때문에 개수만큼 사칙연산을 만들어주었다.
# ex) '+' : 4 -> '+','+','+','+'

def make_overlap(string,number):
    make_list = []
    for i in range(number):
        make_list.append(string)
    return make_list   
 
# 각 사칙연산들의 리스트를 하나의 리스트로 합친 후 조합 생성
# permutation의 경우 중복 허용하기 때문에 set을 사용하여 uniuqe하게 변경

def make_combi(li1, li2, li3, li4):
    li1.extend(li2)
    li1.extend(li3)
    li1.extend(li4)
    return set(permutations(li1,n-1))

# 순서대로 '+','-','*','/'

def plus(x,y):
    return x + y
def minus(x,y):
    return x - y
def multiply(x,y):
    return x * y

# 나눗셈의 경우 조건이 주어짐

def division(x,y):
    if x < 0:
        return -((-x) // y)
    else:
        return x//y

def calculate():
    global number_list
    pl_list = make_overlap('plus',pl)
    mi_list = make_overlap('minus',mi)
    mu_list = make_overlap('multiply',mu)
    di_list = make_overlap('division',di)
    permu_list = make_combi(pl_list, mi_list, mu_list, di_list)
    # deq_number_list = deque(number_list)
    answer_list = []
    for combi in permu_list:
        deq_combi = deque(combi)
        deq_number_list = deque(number_list)
        value = deq_number_list.popleft()
        while deq_number_list:
            a = deq_number_list.popleft()
            sign = deq_combi.popleft()
            if sign == 'plus':
                value = plus(value,a)
            elif sign == 'minus':
                value = minus(value,a)
            elif sign == 'multiply':
                value = multiply(value,a)
            else:
                value = division(value,a)
        answer_list.append(value)
        number_list = number_origin
    return answer_list
        
print(max(calculate()), min(calculate()))