[백준/약점체크] 14888번: 연산자 끼워넣기

이 문제 재밌었다..

 

[문제]

 

[내 코드]

from itertools import permutations
import operator

cnt = int(input()) - 1
arr = list(map(str, input().split()))
ops_cnt = []
for i, j in zip(input().split(), ['+','-','*','/']):
    ops_cnt += [j]*int(i)

cases = list(set(permutations(ops_cnt, cnt)))

def my_div(arg1, arg2):
    if arg1 < 0:
        result = (abs(arg1) // arg2) * (-1)
    else:
        result = arg1//arg2
    return result    
    
ops = {
    '+' : operator.add,
    '-' : operator.sub,
    '*' : operator.mul,
    '/' : my_div,
}

def my_expr(cnt, arr, case):
    result = int(arr[0])
    for c in range(cnt):
        result = ops[case[c]](result, int(arr[c+1]))
    return result

results = []
for case in cases:
    r = my_expr(cnt, arr, case)
    results.append(r)

print(max(results))
print(min(results))

- 616ms

- operator.floordiv 를 썼을 때 오답을 내놓는 문제가 있었다 그래서 따로 my_div 함수를 만들었는데.. 이게 맞나 싶다

- python3 으로 실행했을 때 시간 초과 오류가 나는 문제도 있었다 permutations 한 값들에 set로 중복을 없애는 식으로 해결했다

 

 

[개선안]

- 검색해봤을 때 수열 라이브러리를 사용하면 시간이 오래 걸려 pypy3 으로만 진행할 수 있는 게 사실이었다

- 깊이 우선 탐색(DFS)으로 구현하는 게 모범답안이라고 한다

- DFS에 대한 설명글을 작성했다.

 

cnt = int(input())
arr = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

max_value = -1e9
min_value = 1e9

def dfs(idx, result):
    global max_value, min_value, add, sub, mul, div, cnt
    if idx == cnt:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
    else:
        if add:
            add -= 1
            dfs(idx+1, result+arr[idx])
            add += 1
        if sub:
            sub -= 1
            dfs(idx+1, result-arr[idx])
            sub += 1
        if mul:
            mul -= 1
            dfs(idx+1, result*arr[idx])
            mul += 1
        if div:
            div -= 1
            dfs(idx+1, int(result/arr[idx]))
            div += 1     
            
dfs(1, arr[0])

print(max_value)
print(min_value)

 

- 108ms로 훨씬 빨랐다

- 재귀함수로 구현한다

- 뒤로 가기 해야 하므로 뺐던 1을 다시 더한다

 

이해하려고 애쓴 흔적..