[백준] 14888번 파이썬 _ 연산자 끼워넣기 (삼성SW)

https://www.acmicpc.net/source/31173872

로그인

문제유형 : 완전탐색

 

문제풀이 : 

• 가능한 모든 연산자 순열을 찾는다. itertools의 permutations이용
• 주어진 숫자와 연산자를 식으로 해서 계산한다.
  • 이때 음수를 나눌때만 예외처리를 해줘서 계산한다.

 

기억

• 처음에 숫자와 각각의 연산자 경우에 대해서 둘을 합쳐 하나의 식 형태의 문자열 배열을 만들고, 그 문자열을 eval로 계산하는식으로 했더니 시간초과가 났다. 굳이 문자열로 만든후에 계산하는 이 과정에서 배열을 한번더 돌게되니 시간초과가 난것같다.
• 그래서 그냥 num배열과 op배열을 주고 값을 계산하는 함수를 만들었더니 해결되었다.
  • [1,2,3], [*,//]를 인자로 받아 문제 조건에 맞게 계산 (통과)
  • 이전에는 [1,2,3],[*,//] -> [1,*,2,//,3]으로 만든뒤에 계산 (시간초과)

 

 

정답코드

import sys
from itertools import permutations
input = sys.stdin.readline


#num배열과 op배열
def calculate(num, op):
    while len(num) >1:
        a = num.pop()
        b = num.pop()
        oper = op.pop()
        if int(a)<0 and oper == '//':
            result = str(-eval('-'+a+oper+b))
        else:
            result = str(eval(a+oper+b))
        num.append(result)
    return num[0]


if __name__ == '__main__':
    n = int(input())
    num = list(input().split())
    num = num[::-1]
    op = list(map(int, input().split()))
    dic = {0: '+', 1: '-', 2: '*', 3: '//'}
    op_base = []
    for i in range(4):
        if op[i] != 0:
           for _ in range(op[i]):
               op_base.append(dic[i])

    # 비교대상이될 최대,최솟값
    min_value = int(1e9)
    max_value = -int(1e9)

    # 1. 주어진 연산자를 순서있는 순열로 만든다.
    # 2. 구할수있는 모든 식을 구한다.
    # 3. 주어진 조건에 맞게 계산한다. 나눗셈만 주의
    # 4. 최대,최소를 갱신한다.
    op_set = set()
    for case in permutations(op_base):
        op_set.add(case)

    for case in op_set:
        result = int(calculate(num.copy(), list(case)))

        if result > max_value:
            max_value = result
        if result < min_value:
            min_value = result

    print(max_value)
    print(min_value)