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

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

삼성SW역량테스트 기출문제.

 

연산자를 만들어낼 수 있는 경우의 수를 생성해야 하는데, combinations를 쓰면 (+,*)와 (*,+)가 같은 경우로 인식된다. 모든 경우의 수를 제대로 반영하려면 permutations를 쓸 수 있고, permutations에서 만들어지는 중복 문제는 set() 자료구조로 해결했다.

 

 

	import math
	import sys
	from itertools import permutations
	_ = int(sys.stdin.readline())
	numbers = sys.stdin.readline().split()
	operator_list = list(map(int, sys.stdin.readline().split()))
	operators = {0:"+", 1:'-',2:'*',3:"/"}
	operator_candidate = []
	# 각 operator의 개수를 센다. permutation으로 경우의 수 뽑을 때 활용하기 위해서.
	for i in range(4):
	if operator_list[i] != 0:
	for _ in range(operator_list[i]):
	operator_candidate.append(operators[i])
	# permutation으로 경우의 수 구하기. 중복을 제거하기 위해 set 자료구조를 활용했다.
	candidate = set(permutations(operator_candidate, len(numbers) - 1))
	max, min = -math.inf, math.inf
	for i in candidate:
	# operator가 올 수 있는 경우의 수
	i = list(i)
	stack = []
	for j in range(len(numbers)):
	stack.append(numbers[j])
	if len(stack) == 3:
	# 숫자 / 연산자 / 숫자 형태로 stack에 쌓이면 계산한다.
	temp = int(eval("".join(stack)))
	# 연산 결과를 스택에 다시 저장한다.
	stack = [str(temp)]
	# 마지막 숫자에 도착했으면 끝
	if j == len(numbers)-1:
	break
	else:
	stack.append(i[j])
	# 해당 연산자로 연산을 마친 결과
	answer = eval("".join(stack))
	if answer > max:
	max = answer
	if answer < min:
	min = answer
	print(max)
	print(min)

view raw [백준] 연산자 끼워넣기.py hosted with ❤ by GitHub