연산자끼워넣기

2021.03.30

연산자 끼워 넣기

삼성전자 SW 역량테스트

Solution

완전탐색

모든 연산자 순열에 대해서 연산을 해보고 최소/최댓값을 업데이트하는 방식으로 구현하였습니다.

# make permutation list에서 순열을 만들 때, 그냥 연산자 숫자로 순열을 만들면 중복되는 순열이 생겨서 시간초과가 발생했습니다.

그래서 set으로 먼저 만든 뒤 list로 변환하여 중복이 없도록 하여 해결하였습니다.

---

import sys
sys.stdin = open('input.txt', 'r')

from itertools import permutations
inf = 9999999999

# Brute Force
def solution(N, A, calcPer):
    minRet = inf
    maxRet = -inf
    for calc in calcPer:
        tmp = A[0]
        for n in range(N-1):
            if calc[n] == 0:
                tmp += A[n+1]
            elif calc[n] == 1:
                tmp -= A[n+1]
            elif calc[n] == 2:
                tmp *= A[n+1]
            elif calc[n] == 3:
                if tmp < 0:
                    tmp = -int(abs(tmp) / A[n+1])
                else:
                    tmp = int(tmp/A[n+1])
        minRet = min(minRet, tmp)
        maxRet = max(maxRet, tmp)
    return minRet, maxRet

# input
N = int(input())
A = list(map(int, input().split()))
plus, minus, multi, div = map(int, input().split())

# make permutation list
calcSet = [0 for _ in range(plus)] + [1 for _ in range(minus)] + [2 for _ in range(multi)] + [3 for _ in range(div)]
# calcPer = list(permutations(calcSet, len(calcSet)) 시간초과
calcPer = list(set(permutations(calcSet, len(calcSet))))

# get Result
minResult, maxResult = solution(N, A, calcPer)
print(maxResult)
print(minResult)

---