[백준 python] 14888번 연산자 끼워넣기

문제 링크

14888번: 연산자 끼워넣기

문제 설명

• 순서가 있는 N개의 숫자를 받고 그 숫자 사이에 N-1개의 연산자를 삽입하는 문제
• 중복을 허용하고, 4종류의 연산자로 이루어진 N-1 길이의 순열을 모두 탐색하는 방법으로 접근

고민 한 부분

•  DFS 방식으로 탐색을 하며 이미 탐색한 순열은 다시 탐색하지 않도록 가지치기할 방법 (line 39)

N-1 x 4 크기의 visited 배열을 활용해 depth 번째에 삽입 될 연산자가 이미 사용됐다면 탐색하지 않는 방식으로 탐색 영역을 줄임

 

Lesson learned

max_ = max(max_, result)
min_ = min(min_, result)

• 최대, 최소값을 갱신할 때, python의 내장 함수 max, min을 사용해 코드 길이와 실수를 줄일 수 있음 (line 29~32) 

from itertools import permutations

test_list = [1,2,3,4,5] # 순열을 만들 대상들
L = 3 # 만들 순열의 길이
perm_generator = permutations(test_list, L)

• python에 itertools 모듈에 permutations를 활용하면 list item으로 구성된 N 크기의 순열을 모두 생성하는 generator를 만들 수 있음. 이렇게 풀게되면 시간초과로 통과를 하지 못하지만 간단하기 때문에 먼저 시도해볼만 한 것 같음
• perm_generator를 for문에 사용하거나 next 함수를 사용해 요소를 하나씩 반환할 수도 있음