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

문제
https://www.acmicpc.net/problem/14888
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/14888.%E2%80%85%EC%97%B0%EC%82%B0%EC%9E%90%E2%80%85%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0/%EC%97%B0%EC%82%B0%EC%9E%90%E2%80%85%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0.py

이 문제는 연산자의 순서를 다양하게 조합하여 나온 결과 중 가장 작은 값고 가장 큰 값을 출력하는 문제였다. 따라서 연산자 순서 조합을 모두 탐색해보아야했고, 재귀를 사용하여 코드를 구현하고자 했다.

dfs 함수를 구현하여 dfs 함수를 재귀적으로 사용하였다. 만약 operator 리스트에 남은 연산자가 하나 밖에 없을 경우(operator의 합이 1일 경우)는 연산의 마지막 순서이므로 모든 연산 순서쌍의 결과를 저장하는 result 리스트에 그 값을 저장한다.

마지막 연산이 아닐 경우에는 사용한 연산자에 해당하는 operator 리스트 값을 수정(-1)하고, 연산하고 나온 값을 dfs의 인자값 num1으로 사용하여준다. 그리고 dfs를 호출한 이후, 다른 연산자를 사용한 경우도 구하기 위해 operator 리스트를 이전 상태로 되돌려준다. operator 리스트를 이전 상태로 돌리면 for문에서 다음 차례에 해당하는 연산자에 대하여 dfs 함수가 호출된다. 따라서 모든 조합의경우에 대해서 연산값을 얻을 수 있다.

< 풀이 코드 >

import sys
input = sys.stdin.readline

n = int(input())
number = list(map(int,input().split()))
operator = list(map(int, input().split()))

result = []

def dfs(num1, num2, operator, count):
    if sum(operator) == 1:
        for i in range(len(operator)):
            if operator[i]:
                if i == 0:
                    rst = num1 + num2
                elif i == 1:
                    rst = num1 - num2
                elif i == 2:
                    rst = num1 * num2
                else:
                    if num1 > 0:
                        rst = num1 // num2
                    else:
                        rst = ((-1*num1) // num2) * (-1)
        result.append(rst)
    else:
        for i in range(len(operator)):
            if operator[i]:
                operator[i] -= 1
                if i == 0:
                    rst = num1 + num2
                elif i == 1:
                    rst = num1 - num2
                elif i == 2:
                    rst = num1 * num2
                else:
                    if num1 > 0:
                        rst = num1 // num2
                    else:
                        rst = ((-1*num1) // num2) * (-1)
                dfs(rst, number[count], operator, count+1)
                operator[i] += 1
dfs(number[0], number[1], operator, 2)
print(max(result))
print(min(result))

연산을 하는 부분이 중복되어 나타나서 연산 부분만 따로 함수로 추출하여 코드를 리팩토리했다.

< 풀이 코드 - 연산 함수 추출 >

import sys
input = sys.stdin.readline

n = int(input())
number = list(map(int,input().split()))
operator = list(map(int, input().split()))

result = [] #모든 결과 저장

#연산 함수
def operate(i, num1, num2):
    if i == 0:
        rst = num1 + num2
    elif i == 1:
        rst = num1 - num2
    elif i == 2:
        rst = num1 * num2
    else:
        if num1 > 0:
            rst = num1 // num2
        else:
            rst = ((-1*num1) // num2) * (-1)
    return rst

def dfs(num1, num2, operator, count):
    if sum(operator) == 1: # 마지막 연산
        for i in range(len(operator)):
            if operator[i]:
                rst = operate(i, num1, num2)
        result.append(rst) # 결과값 추가
    else: # 마지막 연산이 아닐 경우 
        for i in range(len(operator)):
            if operator[i]: 
                operator[i] -= 1 # 연산자 사용
                rst = operate(i, num1, num2) 
                dfs(rst, number[count], operator, count+1) # 재귀
                operator[i] += 1  # 다른 연산자 사용한 경우를 위해 사용했던 operator 리스트 이전으로 상태 돌리기

dfs(number[0], number[1], operator, 2)

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