연산자 끼워 넣기 (실버 1) 풀이1-순열

연산자 끼워넣기

 

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

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1 복사

2
5 6
0 0 1 0

예제 출력 1 복사

30
30

---

# 문제 접근

 

주어진 수의 배열 사이에 주어진 연산자를 끼워 넣어 가장 큰 수 와 가장 작은 수를 출력하는 문제이다.

 

평소에 사용하는 연산자 우선순위가 적용되지 않고 앞에서 부터 차례로 계산해야 한다.

 

최댓값은 가장 큰 수 끼리 곱해야 하는 것

 

최솟값은 가장 작은 수 끼리 (마이너스)  곱해야 하는 것

 

하지만 앞에서 부터 계산해야 하는 점 때문에 특정한 문제 패턴을 파악 하지 못했고

 

브루트포스(완전탐색) 알고리즘을 이용하여 전부 계산한 식을 리스트에 append 시킨다음

 

가장 큰 수와 작은 수를 max, min 함수로 출력하도록 코드를 설계해 보았다.

 

---

 

여기서 가장 중요한 모든 경우의 수를 계산하는 방법을 구현 하는 것이다.

 

모든 계산의 경우의 수는 각 N - 1 자리에 N - 1 의 순서를 고려한 경우의 수다.

 

이러한 순서를 고려한 경우의 수를 순열(permutations) 이라고 하며 파이썬은 이러한 순열을 활용할 수 있는 itertools 모듈이 있다.

 

이 모듈을 활용하여 코드 설계

 

 

다른사람의 정답 확인 : https://data-flower.tistory.com/72 

 

---

# 코드 정리

0. 코드 입출력 처리

N = int(input())

nums = list(map(int, input().split())) # 계산할 수의 리스트

cal_input = list(map(int, input().split())) # 각 연산자의 개수 리스트

cal = ["+","-","*","//"]

cal_list = [] # 연산자의 갯수만큼 저장 할 연산자 리스트 (순열을 구하기 위함)

 

1. 연산자의 모든 순열을 구하기.

 

     1-1 연산자의 갯수 만큼 cal_list 리스트에 저장

cal = ["+","-","*","//"]

cal_list = []

for i in range(4):

  if cal_input[i] == 0:

    pass

  else:

    for j in range(cal_input[i]):

      cal_list.append(cal[i])

    1-2 나올 수 있는 순열을 모두 구한다.

num_case = list(permutations(cal_list, len(cal_list)))

 

2. 구한 연산자의 순열로 계산

 

2-1 계산할 연산자의 순서로 사용하기 위해 덱(deque) 사용

queue = deque(num_case)

 

2-1 덱이 모두 사용될 때 까지 연산 수행

while queue: # 큐의 요소가 빌때까지

  current_list = queue.popleft() # 구하기 위한 첫 번째 연산자 꺼내오기

  result = nums[0] # 연산 초기값 

  for i in range(1, len(nums)):

    if current_list[i-1] == '+': # 각 해당 연산자 일 때 연산 수행

      result += nums[i]

    elif current_list[i-1] == '-':

      result -= nums[i]

    elif current_list[i-1] == "*":

      result *= nums[i]

    else:

      if result < 0: # 문제 지시대로 음수의 나눗셈인 경우 처리

        result = -(abs(result)//nums[i])

      else:

        result = result // nums[i]

  max_result = max(result, max_result)

  min_result = min(result, min_result)

 

3. max 함수와 min 함수를 이용하여 최솟값과 최댓값을 출력한다.

print(max_result) #마지막까지 업데이트 최댓값 최솟값 출력

print(min_result)

 

---

 

 

나올 수 있는 모든 연산자의 순서를 모두 구한 후

 

덱 자료구조를 이용하여 모든 연산을 수행 

 

수행한 결과에 따라 최댓값일 경우 result 변수를 업데이트

 

모든 연산을 수행하는 이유 때문에 브루트 포스 알고리즘 문제에 해당된다.

 

구한 순열에 따라 연산을 하는 코드를 구현해내지 못해 다른 사람의 정답을 활용하였다.

 

하지만 이 코드는 정답이지만, 순열을 구하는 pernutations 연산의 시간복잡도가 높기때문에 완벽한 정답이 아니다.

 

파이썬코드로 제출 하면 시간초과가 발생한다.

 

 

이 문제의 다른 풀이 인 DFS를 활용한 코드를 적용해 보겠다.