연산자 끼워넣기 (3)

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

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 1021 555 435 56.714%
문제
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
식의 계산은 연산자 우선 순위를 이용해 계산해야 한다. 연산자 우선 순위는 ×와 ÷가 +와 -보다 앞선다. 우선 순위가 같은 경우에는 앞에 있는 식을 먼저 계산한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 3
1÷2+3+4-5×6 = -23
1+2÷3×4-5+6 = 2
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억보다 작거나 같다.

DFS로 리스트 만들어서 연산자 우선순위 따지면 되는 간단한 문제이다.

기존 정답 코드는 다음과 같은 흐름을 가진다.

1. DFS를 돌리면서 배열을 만든다.
2. 만들어진 배열로 곱/나누기 계산을 먼저한다.
3. 이후 +,- 계산을 한다.

파이썬 기준 160ms정도 나왔다.
문제는 여기서 어떻게 더 최적화를 할 수 있느냐?이다.

일단 배열을 만들고 계산하는 코드가 길어지는데,
약 40줄의 코드가 나와버린다.
숏코딩으로 억지로 줄일려면 줄일수는 있겠지만 가독성이 박살날 것이다.

1등한 분의 코드를 뜯어보면 이 문제를 재미있게 해석하셨다.

1. 이전/이후 숫자를 비교한다.
2. +,-라면 계산을 보류하고, *,//라면 먼저 계산한다.
3. 중요한건 +,-끼리 계산할 수 있도록 '보류'한다.

말만 들어도 뭔소린지 잘 감이 안오는데, 코드를 봤을때도 해석하는데 시간이 걸렸다.
잠깐에 불과했지만 간단한 코드에도 '해석'이 필요하다는거 부터가
최적화가 들어가면 코드의 가독성이 낮아진다는 소리다.

그리고 마지막 eval 함수이다.

import sys
input = sys.stdin.readline

def dfs(index, op):
    global Max, Min
    if index == N-1:  
        result = eval(op)
        Max = max(Max, result)
        Min = min(Min, result)
        return

    for i in range(4):
        if signs[i] > 0:
            signs[i] -= 1
            N_op = op + op[i] + str(numbers[index + 1])
            dfs(index + 1, N_op)
            signs[i] += 1

N = int(input())
numbers = list(map(int, input().split()))
signs = list(map(int, input().split())) 
op = ['+', '-', '*', '//']  

Max = -float('inf')
Min = float('inf')

dfs(0, str(numbers[0]))

print(Max)
print(Min)

입출력과 로직까지 30줄 안에 끝났다.
그냥 str으로 리스트 만들고 eval로 계산하면 끝난다.

코드의 길이는 줄었지만 등가교환으로 시간이 배 이상으로 늘었다.
파싱하는데 시간이 좀 오래 걸리나 보다.

그리고 이전 코테용 파이썬 정리 글에서도 썼었는데, eval 함수는 그냥 안쓰는게 좋다.
코테에서 썼다가 면접에서 뭔 질문이 날아올지도 모르고 왠만하면 eval써서 풀리는건
로직으로 충분히 구현 가능하기 때문이다.

일반적으로 eval을 검색했을때 나오는 말들은

• eval 쓰면 가독성 나빠진다
• eval 쓰면 보안이 취약해진다

2가지 위험성이 존재한다.

• 하지만 input의 무결성 검사를 마쳤다면
• 성능이 상관없을정도로 계산량이 작다면
• eval로 로직 구현하는게 훨씬 간단하다면

eval을 써도 괜찮지않을까? 하는 생각을 하게 되었다.

왜냐면 eval의 injection 공격 레퍼토리를 검색해 보아도
client가 eval을 통해 명령어를 input하는 경우가 대부분이다.

그래서 eval에 input값을 직접 넣는것이 아닌, 특정한 로직을 통해 계산한 결과값을
eval로 실행시키는 등의 방법을 쓰면 injection이 발생할 확률이 0에 가깝다.
알고리즘 문제에서 푸는 것처럼

lst = list(map(int,input().split()))
for i in lst:
	~~~

위와 같이 특정한 값을 받고, 그 로직을 실행시켜야 하는데
여기에 커맨드를 입력해도 로직이 실행되지 않기 때문이다.

물론 이런 경험이 있었다고 해서 eval을 직접 쓰는일은 절대 없을 것이다.
어떻게 버그가 터질지 모르는 프로그래밍에서 굳이 리스크를 가져가야할 이유는 전혀 없기 때문이다.

하지만 eval이 아닌 다른 기술에서, 이런 tradeoff상황이 발생할때 어떻게 대처할 것인가?
그런 생각을 오래 하게 된 문제인거 같다.