14888 연산자 끼워넣기 (파이썬 시간초과)

이 문제는 이코테 책에서 DFS/BFS 파트의 문제인데 조합으로도 풀이가 가능해서 `itertools` 라이브러리의 `permutations`클래스를 사용해서 풀었다.

 

하지만 Python3로 제출했지만 시간초과 발생

from itertools import permutations
n = int(input())
lst = list(map(int,input().split()))
op_cnt = list(map(int,input().split()))
op = ['+', '-', '*', '%']
op_idx = []
for cnt, op_symbol in zip(op_cnt, op):
  for i in range(cnt):
    op_idx.append(op_symbol)
op = list(permutations(op_idx, n-1))
result = lst[0]
max = -1e+10
min = 1e+10
for op_symbol_list in op:
  result = lst[0]
  for o, num in zip(op_symbol_list, lst[1:]):
    if o == '+':
      result += num
    elif o == '-':
      result -= num
    elif o == '*':
      result *= num
    elif o == "%":
      if result < 0:
        result = abs(result) // num
        result = -result
      else:
        result //= num
  if max < result:
    max = result
  if min > result:
    min = result
print(max)
print(min)

 

백준 질문 게시판(https://www.acmicpc.net/board/view/139406)을 보니까 질문자님의 의도와 내 의도가 정확히 일치했다. 좀 더 최적화를 하고 싶어서 python3으로 제출해서 정답을 얻고 싶었다. 

 

하지만 이 글을 보고 굳이 최적화를 하지 않아도 될 거 같다는 생각이 들어서 그냥 pypy3로 제출했다...ㅋㅋㅋㅋ

백준은 python에 친화적이지 않고, 코테에서 파이썬으로도 풀 수 있도록 시간제한을 걸어놓는 다는 거에서 굳이 머리싸매서 최적화에 신경쓸 필요를 느끼지 못했다.