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

⏱️ 소요시간

1시간. 아직 재귀함수를 작성하는 것을 잘 못하는 것 같다.

📚 문제 요약

[백준] 14888. 연산자 끼워넣기
첫째줄에는 숫자의 개수, 둘째줄에는 숫자, 세번째 줄에는 연산자의 개수를 입력으로 받는다.
숫자의 순서는 그대로, 연산자는 순서를 바꿔가며 연산했을 때 나올 수 있는 결과값 중에서 최대값과 최소값을 출력

📑 풀이 요약

1. 입력받은 연산자의 개수를 이용하여 연산자만 들어있는 리스트 하나를 만든다.
2. permutation을 이용하여 연산자 경우의 수들을 모두 구해본다.
3. 2번에서 뽑은 연산자 순서대로 계산을 한다.
4. 이 때 내가 시도했던 연산자 순서인 경우에는 건너뛰고 그렇지 않은 경우에만 계산 진행 (시도했던 연산자인지 확인하기 위해서 set 자료형 사용)
5. 연산 진행!

🌟 내가 만난 어려웠던 점

시간 초과 문제
겹치는 경우를 고려하지 않았다. 예를 들어 연산자 배열이 [+, +, -, -] 라고하고 이 때 인덱스는 당연히 0, 1, 2, 3이다. permutation으로 뽑아보면
0 1 2 3
0 1 3 2
0 2 1 3
...
인데
0 1 2 3 인 경우 연산자 배열은 [+, +, -, -] 이고
0 1 3 2 인 경우도 연산자 배열은 [+, +, -, -] 이다!

즉 permutation으로 모든 경우의 수를 다 계산하는 게 아니라, 이전에 계산한 연산자 순서인 경우에는 pass 해줘야 하므로 이 순서대로 연산을 진행했는지 check하는 과정이 필요하다

🖥️ 전체 코드

from itertools import permutations
import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
tools = list(map(int, input().split()))
c = []
visited = set([])
for i in range(4):
    if i == 0 and tools[i] > 0:
        for _ in range(tools[i]):
            c.append('+')
    elif i == 1 and tools[i] > 0:
        for _ in range(tools[i]):
            c.append('-')
    elif i == 2 and tools[i] > 0:
        for _ in range(tools[i]):
            c.append('*')
    elif i == 3 and tools[i] > 0:
        for _ in range(tools[i]):
            c.append('/')
maximum = -1000000001
minimum = 1000000001

for i in permutations(c, n-1):
    res = numbers[0]
    if i in visited:
        continue
    visited.add(i)
    for j in range(n-1):
        if i[j] == "+":
            res = res + numbers[j+1]
        elif i[j] == '-':
            res = res - numbers[j+1]
        elif i[j] == '*':
            res = res * numbers[j+1]
        elif i[j] == '/':
            if res < 0:
                res = -1*(((-1)*res) // numbers[j+1])
            else:
                res = res // numbers[j+1]
    if res > maximum:
        maximum = res
    if res < minimum:
        minimum = res

print(maximum)
print(minimum)