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

실버 1 - https://www.acmicpc.net/problem/14888

Code

# 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행
# 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하기

from itertools import permutations

n = int(input())    # 수의 개수
nums = list(map(int, input().split()))  # 연산을 진행할 숫자들
ops = list(map(int, input().split()))   # + - * / 개수

ans = list()    # 계산한 값을 담는 리스트

ops_list = ['+', '-', '*', '/']
ops_johap = []      # 연산자들의 개수만큼 각 연산자들을 순서대로 담을 리스트

for i in range(len(ops)):
    if (ops[i] == 0):
        continue
    for j in range(ops[i]):
        ops_johap.append(ops_list[i])

ops_johap_permutation = list(permutations(ops_johap, len(ops_johap)))   # 연산자들의 순서별 조합들

# 연산자 순서별로 나오는 결과 저장
max_total = -(10 ** 10)
min_total = 10 ** 10
for p in range(len(ops_johap_permutation)):
    ops_select = ops_johap_permutation[p]   # 선택된 연산자 조합

    # 연산식 만들어서 계산
    total = nums[0]
    for i in range(n - 1):
        if(ops_select[i] == '+'):
            total += nums[i+1]
        if (ops_select[i] == '-'):
            total -= nums[i+1]
        if (ops_select[i] == '*'):
            total = int(total * nums[i+1])
        if (ops_select[i] == '/'):
            total = int(total / nums[i+1])

    if(total < min_total):
        min_total = total
    if(total > max_total):
        max_total = total

### eval() 사용해서 계산하는 방법
# for p in range(len(ops_johap_permutation)):
#     ops_select = ops_johap_permutation[p]   # 선택된 연산자 조합
#     start = int(eval(str(nums[0]) + ops_select[0] + str(nums[1])))   # 시작값 (첫번째 연산자 계산)
#
#     # 연산식 만들어서 계산
#     total = start
#     for i in range(1, n - 1):
#         if (i < n-1):
#             # print(str(total) + ops_select[i] + str(nums[i+1]))
#             total = int(eval(str(total) + ops_select[i] + str(nums[i+1])))
#     if(total < min_total):
#         min_total = total
#     if(total > max_total):
#         max_total = total
#     # ans.append(total)

# 정답 출력
print(max_total)
print(min_total)

풀이 및 해설

• 시간초과 해결
  • Python3로 하면 시간초과 나서 Pypy3로 풀어야함
  • eval()도 TLE난다고 어디서 봄,,, 그래서 코드 변경
• 연산자들의 개수만큼 순서 별 조합을 구해서 차례대로 계산해주기 → 최대값이면 업데이트, 최소값이면 업데이트
• 해맸던 포인트
  • 오랜만에 쓰는 itertools

    # 연산자들의 순서별 조합들
    ops_johap_permutation = list(permutations(ops_johap, len(ops_johap)))   

  • 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.
  • 이 과정에서 max와 min의 초기값을 아래와 같이 설정해주어야 했다.

    max_total = -(10 ** 10)
    min_total = 10 ** 10

What I learned

eval() : 문자열 연산하기
참고 : https://itinformation.tistory.com/110