[BOJ] 14888번 연산자 끼워넣기 / 사용언어 : 파이썬(python)

※ 문제링크

14888번: 연산자 끼워넣기

※ 관련 알고리즘 설명 

[알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)

※ 문제풀이(실패사례)

N = int(input())
number_list = list(map(int, input().split())) # 입력받은 숫자들로 리스트를 생성
pu, mi, mul, div = map(int, input().split())
operator_list = ['+' for _ in range(pu)] + ['-' for _ in range(mi)] + ['*' for _ in range(mul)] + ['/' for _ in range(div)] 

check_list = [False] * (N-1)
operator_combination = ''
result_list = []


def dfs():
    global operator_combination
    if len(operator_combination) == (N-1):
        if operator_combination not in result_list:
            result_list.append(operator_combination)
        return
    
    for i in range(N-1):
        if check_list[i]:
            continue
         
        check_list[i] = True
        operator_combination += operator_list[i]

        dfs()

        operator_combination = operator_combination[:-1]
        check_list[i] = False
dfs()   

maxValue = 0
minValue = 0
for i in range(len(result_list)):
    value = number_list[0]
    for k in range(N-1):
        if result_list[i][k] == '+':
            value += number_list[k+1]
        elif result_list[i][k] == '-':
            value -= number_list[k+1]
        elif result_list[i][k] == '*':
            value *= number_list[k+1]
        elif result_list[i][k] == '/':
            if value < 0 and number_list[k+1] < 0: 
                value = int(abs(value) // abs(number_list[k+1]))
            elif value < 0 or number_list[k+1] < 0:             
                value = int(abs(value) // abs(number_list[k+1])) * (-1)                
            else:
                value = int(abs(value) // abs(number_list[k+1]))
    if i == 0:
        maxValue = value
        minValue = value
    else:
        if value > maxValue:
            maxValue = value
        if value < minValue:
            minValue = value
print(maxValue, minValue, sep= '\n')

 

해당문제는 백트래킹과 DFS를 활용하여 푸는 문제였다. 처음에는 아래와 같은 순서로 문제를 풀려고 시도를 했었다.

1. 입력값으로 숫자 리스트 생성, 연산자 리스트 생성

2. DFS와 백트래킹, 조건문을 통한 연산자 리스트 생성

3. 연산자리스트와 숫자 리스트 조합수를 작성하여 결과값 도출

결과값자체는 샘플테스트 결과 정상적으로 출력되었지만 시간초과가 나왔다.해당 코드를 수정하기 위해 구글링을 했고, 구글링을 한 결과 기본 개념과 구현자체는 비슷하나 코드를 실행하고 출력하는 것에있어서 비효율성이 발생한다는 것을 확인하여, 기존에 작성되어 있는 코드를 보면서 어떤 방식으로 작성을 하고 있는지 확인하였다.

 

※ 문제풀이(성공사례)

import sys
 
n = int(input())
number_list = list(map(int, input().split()))
# 연산자 각각의 갯수를 저장
pu, mi, mul, div = map(int, input().split())
maxValue, minValue = -100000001, 1000000001 # 최댓값과 최솟값의 크기에 맞춰 작성
 
def dfs(i, res, pu, mi, mul, div):
    global maxValue, minValue
    if i == n-1: 
    # 최초 max_num가 범위를 벗어나는 최솟값이고, 최초 min_num가 범위를 벗어나는 최댓값임
        if res > maxValue:
            maxValue = res
        if res < minValue:
            minValue = res
        return
 
    else: # 재귀 호출을 통한 모든 경우의 수 탐색
        if pu:
            dfs(i + 1, res + number_list[i+1], pu - 1, mi, mul, div) 
            # +가 먼저 들어가게끔 계산 후 -, *, /순으로 연산수행 - 예시 1+2+3-4*5/6
        if mi:
            dfs(i + 1, res - number_list[i+1], pu, mi - 1, mul, div) 
            # -가 먼저 들어가게끔 계산 후 +, *, /순으로 연산수행 - 예시 1-2+3+4*5/6
        if mul:
            dfs(i + 1, res * number_list[i+1], pu, mi, mul - 1, div) 
            # *가 먼저 들어가게끔 계산 후 +, -, /순으로 연산수행 - 예시 1*2+3+4-5/6
        if div:
            dfs(i + 1, int(res / number_list[i+1]), pu, mi, mul, div - 1) 
dfs(0, number_list[0], pu, mi, mul, div)
print(maxValue, minValue, sep='\n')

 

처음 코드를 봤을 때는 바로 이해가 되지는 않았지만 하나하나 중간중간에 출력문을 걸어가며 어떤식으로 코드가 작동하고 있는지 확인을 하며, 이해하려고 하였고, 고민했던 부분들이 해소된 곳에는 주석을 달아보았다. 이번 문제를 풀며 효율적인 구현은 계속 시도하고 고민하여 자신의 것으로 만들어야 가능하겠다라는 생각을 상기할 수 있었다.

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.