[Baekjoon Online Judge] 백준 14888번 연산자 끼워넣기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 14888번 연산자 끼워넣기

(Python)

(글쓴날 : 2020.04.03)

 

---

* Baekjoon Online Judge, 백준 14888번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 14888번 연산자 끼워넣기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

2) 풀이 과정

N개의 수로 이루어진 수열이 주어지고 사용 가능한 연산자들이 주어질 때 수열과 연산자를 조합한 결과의 최댓값과 최솟값을 출력하는 문제입니다.

 

저의 경우, DFS를 적용하여 문제에 접근했으며, N - 1개 만큼의 가능한 연산자의 순열을 구해 주어진 수열에 조합하여 최댓값과 최솟값을 구해 문제를 해결했습니다.

단, 나눗셈의 경우 예외 케이스가 하나 있는데, 음수를 양수로 나눌 때는 C++14의 기준을 따라 음수를 양수로 바꾼 뒤 몫을 구하고 다시 그 몫을 음수로 바꿔야 합니다.

 

또한, Python 3로는 시간 초과가 발생하였으며, PyPy3로 정답 처리가 되었습니다. 아무래도 최댓값과 최솟값의 한도가 -10억 ~ 10억이다 보니 Python3로는 버티지 못하는 것 같습니다.

 

Python 3 시간초과, PyPy3 맞았습니다!!

---

3) 코드

 

* Python 코드(PyPy3)

import sys
input = sys.stdin.readline
 
 
def DFS():
    global N, nums, visit, opers, stack, maximum, minimum
 
    if len(stack) == N - 1:
        result = nums[0]
        for i in range(1, len(nums)):
            if stack[i - 1] == "+":
                result += nums[i]
            elif stack[i - 1] == "-":
                result -= nums[i]
            elif stack[i - 1] == "*":
                result *= nums[i]
            else:
                if result < 0:
                    result = -(abs(result) // nums[i])
                    continue
                result //= nums[i]
        
        if result > maximum:
            maximum = result
        if result < minimum:
            minimum = result
    
    for i in range(len(opers)):
        if not visit[i]:
            visit[i] = True
            stack.append(opers[i])
            DFS()
            visit[i] = False
            stack.pop()
 
 
N = int(input())
nums = list(map(int, input().split()))
operCount = list(map(int, input().split()))
visit = [False] * sum(operCount)
opers = []
stack = []
maximum = -1000000000
minimum = 1000000000
 
for index, value in enumerate(operCount):
    for _ in range(value):
        if index == 0:
            opers.append("+")
        elif index == 1:
            opers.append("-")
        elif index == 2:
            opers.append("*")
        else:
            opers.append("/")
 
DFS()
 
print(maximum)
print(minimum)

---