[백준 14888번] 연산자 끼워넣기 - 파이썬

문제 링크:

 

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

14888번: 연산자 끼워넣기

 

---

풀이 유형:

브루트포스 알고리즘, 백트래킹, 깊이 우선 탐색, 너비 우선 탐색

 

풀이 과정:

이 문제의 풀이 과정은 2가지가 있다.

 

★ 첫 번째 방법은 필자가 풀은 방법인 순열 라이브러리와 BFS를 이용한 방법이다.

먼저 연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입한다.

(예를 들어 '+', '-', '+', 'x' 4가지 연산자가 있다면 24가지(=4!) 경우의 수를 모두 비교한다.)

이후에 완전탐색을 이용해 큐에서 하나씩 꺼내어 계산하고 이를 최댓값과 최솟값과 비교 후 값을 업데이트해준다.

이 방법의 단점은 시간 복잡도가 많이 소요되므로 PyPy3에서만 성공이 되고, Python3에서는 시간 초과가 뜬다.

 

★★ 두 번째 방법은 파이썬의 라이브러리를 사용하지 않고 DFS로만 푸는 방법이다.

DFS로 이용하는 방법은 첫 번째 방법보다 시간복잡도가 훨씬 낮으며, 모범 답안에 속한다. 

DFS 매서드 함수에 입력받은 수열의 개수만큼 계속 반복해서 재귀적으로 함수를 수행하면 된다.

 

2가지 방법의 메모리와 시간복잡도 비교

첫 번째 줄의 메모리와 시간은 두 번째 방법인 DFS를 이용한 방법이며. 시간은 112ms로 Python3에서 원활하게 작동된다.

반면 두 번째 줄의 순열과 BFS를 이용한 방법은 PyPy3에서만 작동되며, 시간복잡도가 2888ms로 상당히 많이 소요됨을 알 수 있다.

 

풀이 코드:

첫 번째 방법: 순열과 BFS 이용

# 14888번 연산자 끼워 놓기

# 파이썬에서의 순열 라이브러리 이용
from itertools import permutations
from collections import deque

n = int(input())
seq = list(map(int, input().split()))

# 연산자 
cal = ['+', '-', '*', '//']
# 연산자 입력받기
cal_input = list(map(int, input().split()))
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])

# 만들 수 있는 모든 연산자 배열의 경우의 수
num_case = list(permutations(cal_list, len(cal_list)))
q = deque(num_case)

# 최댓값, 최솟값 초기화
max_result = -1e9
min_result = 1e9

# 큐가 빌 때까지 모든 경우의 수에 대해 연산 수행
while q:
  # 연산자들에 대하여 
  now_list = q.popleft()
  result = seq[0]
  # 차례로 연산 수행
  for i in range(1, len(seq)):
    # 연산자가 더하기라면
    if now_list[i-1] == '+':
      result += seq[i]
    # 연산자가 빼기라면
    elif now_list[i-1] == '-':
      result -= seq[i]
    # 연산자가 곱하기라면
    elif now_list[i-1] == '*':
      result *= seq[i]
    # 연산자가 나누기라면
    else:
      if result < 0:
        result = -(abs(result) // seq[i])
      else:
        result = result // seq[i]    
  # 최댓값, 최솟값 계산      
  max_result = max(max_result, result)
  min_result = min(min_result, result)

# 결과 출력
print(max_result)
print(min_result)

 

두 번째 방법: DFS 이용

# 14888번 연산자 끼워 놓기
# dfs 이용

# 수의 개수 입력받기
n = int(input())
# 수열 입력받기
data = list(map(int, input().split()))
# 연산자 개수 계산
add, sub, mul, div = map(int, input().split())

# 최댓값과 최솟값 초기화
max_value = -1e9
min_value = 1e9

# dfs 매서드 정의
def dfs(i, arr):
  global add, sub, mul, div, max_value, min_value
  # 주어진 수열을 다 받았을 경우 최댓값과 최솟값 계산
  if i == n:
    max_value = max(max_value, arr)
    min_value = min(min_value, arr)
  else:
    # 더하기
    if add > 0:
      add -= 1
      dfs(i+1, arr + data[i])
      add += 1
    # 빼기
    if sub > 0:
      sub -= 1
      dfs(i+1, arr - data[i])
      sub += 1
    # 곱하기
    if mul > 0:
      mul -= 1
      dfs(i+1, arr * data[i])
      mul += 1
    # 나누기
    if div > 0:
      div -= 1
      dfs(i+1, int(arr / data[i]))
      div += 1
  
# DFS 메서드 호출
dfs(1, data[0])

# 최댓값과 최솟값 출력
print(max_value)
print(min_value)

 

14888번 연산자 끼워 놓기