[BaekJoon] 14888번 : 연산자 끼워넣기

14888번 : 연산자 끼워넣기

주어진 연산자 개수를 가지고 가능한 모든 순열을 만들어 계산을 하면 된다.

중복되는 연산자가 있는 경우 permutation 으로 순열을 구하게 되면 (+, +) , (+, +) 를 다른 것으로 인식 한다.

따라서 순열을 만든 뒤 set 으로 중복 되는 값을 지우고 시작하면 된다.

하지만 permutation 을 통해 풀면 시간이 굉장히 오래 걸린다.

n 의 수가 조금만 더 커져도 바로 시간초과가 발생할 것 이다.

재귀를 통한 DFS 로 풀 수도 있는데 그 방법은 복습 할 때 사용 해야겠다.

---

from itertools import permutations


def calc_formula(nums, opers):
	nums = list(reversed(nums))
	opers = list(reversed(opers))

	while opers:
		a, oper, b = nums.pop(), opers.pop(), nums.pop()
		if int(a) < 0 and oper == '//':
			a = str(-int(a))
			formular = a + oper + b
			nums.append(str(-eval(formular)))
			continue

		formular = a + oper + b
		nums.append(str(eval(formular)))

	return int(nums[0])


def solution(n, nums, oper_cnt):
	answer_max = -float('inf')
	answer_min = float('inf')
	opers = []
	for oper, cnt in zip(['+', '-', '*', '//'], oper_cnt):
		opers.extend([oper] * cnt)

	for permutation in set(permutations(opers, n - 1)):
		num = calc_formula(nums, permutation)
		if num > answer_max:
			answer_max = num
		if num < answer_min:
			answer_min = num

	print(answer_max)
	print(answer_min)


if __name__ == '__main__':
	n = int(input())
	nums = list(input().split())
	oper_cnt = list(map(int, input().split()))

	solution(n, nums, oper_cnt)