[파이썬]백준 14888 연산자 끼워넣기

링크

백준 14888 연산자 끼워넣기

조합을 재귀를 이용해서 구하는게 아닌 함수를 사용해서 풀었다.
사칙연산자의 리스트를 만들고 조합을 구한 후
zip()을 사용해 자리에 맞는 숫자와 묶은 후 연산자의 종류를 탐색하며 ans에 누적계산을 해주었다.

첫번째 시도는 시간초과가 떴다.
사칙연산자는 4개이기 때문에 연산자의 자리만 바뀐 경우 동일한 계산을 하게 돼 중복이 발생하기 때문이다.

pypy로 시도하니 돌아가긴 하지만 시간이 너무 오래걸렸다.

이를 해결하기 위해 연산자 조합을 만들때 set()으로 중복을 제거한 후 zip()으로 묶기 위해 다시 iterable한 요소(list)로 바꿔주었다.
이렇게 하니 pypy의 1/6시간에 풀 수 있었다.

정답 코드

import itertools
import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
opr_num = list(map(int, sys.stdin.readline().split()))
opr = []
# 1 == +, 2 == -, 3 == *, 4 == /
for i in range(4):
    while opr_num[i] != 0:
        opr.append(i + 1)
        opr_num[i] -= 1

perm = list(set(itertools.permutations(opr, N - 1))) #중복제거해주니까 통과했음 기존에 list론 통과안댐
rest = num[1:]
min = 1000000000
max = -1000000000
for i in range(len(perm)):
    ans = num[0]
    tmp = list(zip(perm[i], rest))
    for j in range(N - 1):
        if tmp[j][0] == 1:
            ans += tmp[j][1]
        if tmp[j][0] == 2:
            ans -= tmp[j][1]
        if tmp[j][0] == 3:
            ans *= tmp[j][1]
        if tmp[j][0] == 4:
            ans = int(ans / tmp[j][1])
    if ans > max:
        max = ans
    if ans < min:
        min = ans

print(max, min, sep='\n')

알게된 것👨‍💻

• 중복이 많은 경우 중복제거를 위해 set()을 사용하는 것을 고려해보자