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

📌 문제 링크

연산자 끼워넣기

📌 코드

// 2452ms
// 순열을 이용한 풀이

from itertools import permutations
import sys

input = sys.stdin.readline
N = int(input())
numbers_lst = list(map(int, input().split()))
operator_lst = []

for idx, counter in enumerate(list(map(int, input().split()))):
    operator = ''
    if idx == 0: operator = '+'
    elif idx == 1: operator = '-'
    elif idx == 2: operator = '*'
    elif idx == 3: operator = '/'
    for n in range(counter):
        if operator: operator_lst.append(operator)

operator_permutations_lst = list(permutations(operator_lst, len(operator_lst)))
operator_remove_overlap_set = set(operator_permutations_lst)

result = []
for operator in operator_remove_overlap_set:
    value = numbers_lst[0]
    for idx, op in enumerate(operator, 1):
        if op == '+': value += numbers_lst[idx]
        elif op == '-': value -= numbers_lst[idx]
        elif op == '*': value *= numbers_lst[idx]
        elif op == '/': value = int(value / numbers_lst[idx])

    result.append(value)

print(max(result))
print(min(result))

📌 해설 참조 후 생각 정리

1. 해설을 참조했을 때 순열을 이용한 방법과 DFS를 이용한 방법이 있었다.
2. 두 가지 궁금증이 생겼다. 첫번째는 똑같이 순열을 이용해 풀었는데 내 풀이의 시간 복잡도는 2000대이고 참조 풀이는 900대여서 왜 그런지 궁금했고 DFS를 통해 풀면 시간복잡도가 기존보다 10배가 내려가는 것이 궁금했다.
3. 똑같은 순열을 사용해도 시간복잡도가 달랐던 이유에 있어 참조 소스코드는 permutaion의 결과값을 리스트로 변환하지 않았기 때문이었다. 나는 list로 바꾸고 set으로 바꾸는 작업을 하며 시간 복잡도는 물론 메모리까지 많이 사용하였다. => permutaion을 통해 순회할 때 무조건 list나 다른 자료구조로 변환해야하는 줄 알았는데 굳이 그렇게 하지 않아도 된다는 사실을 알게되었다.
4. DFS를 통해 푸는 방법이 순열을 이용해 푸는 방법보다 시간 복잡도가 낮은 이유는 순열 라이브러리가 시간 복잡도(n!(전체 개수) / n! - r!(필요한 개수))를 많이 잡아 먹어서 그런게 아닐까 예상을 해본다.

📌 해설 참조 코드

// 936ms
// 순열을 이용한 풀이

from itertools import permutations
import sys

input = sys.stdin.readline
N = int(input())
numbers_lst = list(map(int, input().split()))
operator_lst = []

for idx, counter in enumerate(list(map(int, input().split()))):
    operator = ''
    if idx == 0: operator = '+'
    elif idx == 1: operator = '-'
    elif idx == 2: operator = '*'
    elif idx == 3: operator = '/'
    for n in range(counter):
        if operator: operator_lst.append(operator)

maximum = -1e9
minimum = 1e9

for operator in permutations(operator_lst, len(operator_lst)):
    value = numbers_lst[0]
    for idx, op in enumerate(operator, 1):
        if op == '+': value += numbers_lst[idx]
        elif op == '-': value -= numbers_lst[idx]
        elif op == '*': value *= numbers_lst[idx]
        elif op == '/': value = int(value / numbers_lst[idx])

    if value > maximum:
       maximum = value
    if value < minimum:
       minimum = value

print(maximum)
print(minimum)

// 276ms
// DFS를 이용한 풀이

import sys

input = sys.stdin.readline
N = int(input())
numbers_lst = list(map(int, input().split()))
operator_lst = list(map(int, input().split()))

min_value = 1e9
max_value = -1e9

def calc(depth, sum_value, idx):
    if idx == 0: new_sum_value = sum_value + numbers_lst[depth]
    elif idx == 1: new_sum_value = sum_value - numbers_lst[depth]
    elif idx == 2: new_sum_value = sum_value * numbers_lst[depth]
    else: new_sum_value = int(sum_value / numbers_lst[depth])

    operator_lst[idx] -= 1
    dfs(depth + 1, new_sum_value)
    operator_lst[idx] += 1

def dfs(depth, sum_value):
    global max_value, min_value

    if depth == N:
        max_value = max(max_value, sum_value)
        min_value = min(min_value, sum_value)

    if operator_lst[0] > 0: calc(depth, sum_value, 0)
    if operator_lst[1] > 0: calc(depth, sum_value, 1)
    if operator_lst[2] > 0: calc(depth, sum_value, 2)
    if operator_lst[3] > 0: calc(depth, sum_value, 3)


dfs(1, numbers_lst[0])
print(max_value)
print(min_value)

📌 문제 풀어본 후기

📌 출처

연산자 끼워넣기 해설 출처