[프로그래머스] 코딩테스트 연습 - 사칙연산(Python)

코딩테스트 연습 - 사칙연산 [찾아라 프로그래밍 마에스터]

풀이

저는 개인적으로 정말 어려웠던 문제였습니다. 처음 시도했던 방법은 순열이었습니다. 풀다가 생각해보니 순열로 풀려면 모든 연산자에 대해 순열이 필요하고 100개의 연산자가 있으면 반복해야 하는 횟수가 너무 많아지더라고요. 

그래서 다른 방법을 생각하다가 DP로 최소, 최대값을 저장하면서 풀면 되겠다 싶었는데 코드를 짜는 것이 쉽지만은 않아서 결국 질문하기에 풀이를 공유해주신 분의 c++코드를 참고해서 풀었습니다ㅎㅎ..

 

미흡하겠지만 제가 이해한 것들을 바탕으로 설명을 해보겠습니다.

먼저 풀이에 대해 간단하게 설명해보자면 풀이를 공유해주신 분의 방식과 같이 식을 뒤에서 부터 읽으며 -를 만났을 때에는 최댓값과 최솟값을 갱신하고 +를 만나면 이전 -부터 다음 -까지 숫자를 더해 식을 계산해나가는 방식으로 풀이했습니다.

상세하게 풀이를 설명하기 전 -의 특징에 대해 설명해보자면 다음과 같습니다.

• -연산은 뒤에 있는 식에 영향을 미치는 3가지 경우가 있습니다.
  • 식 : a-b+c-d 를 예로 들어 b 앞의 -를 기준
    • [1번 경우] a-(b+c-d) : 식 전체에 영향을 미치는 경우
    • [2번 경우] a-(b+c)-d : 다음 -전까지의 식에 영향을 미치는 경우
    • [3번 경우] a-(b)+c-d : -바로 뒤의 숫자에만 영향을 미치는 경우
• -뒤의 전체식의 최소값과 최댓값을 알아야 합니다.
  • -가 여러번 등장하면 영향을 미치는 식들에 부호가 반전되므로 양의 최댓값이 -를 만나면 최솟값으로 음의 최솟값이 -를 만나면 최댓값으로 변하게 됩니다.

최댓값과 최솟값을 알아야 한다는 것을 알았으니 -부터 뒤의 식에 대해 최대 최소를 어떻게 구해야 할지 알아야겠죠.

앞서 말한 것처럼 최대 최소를 계산할 때 -를 만날 때까지 +들의 값을 계산하고 뒤의 -(식)에 대해 최대 최소를 알고 있습니다.

그렇다면 식은 -SUM(현재 인덱스 ~ 이전 -의 바로 앞 인덱스) + (최대 or 최소)가 되겠죠. 이때 -가 영향을 미치는 경우를 보면

[1번 경우] "-(sum + 최대or최소)",

[2번 경우] "-(sum) + 최대or최소",

[3번 경우] "-(sum[0]) + sum[1:] + 최대or최소" (편의상 sum에 계산되는 list의 인덱스를 사용) 가 됩니다.

 

이때 최솟값은 -방향으로 최대한 크게 만들면 되니 [1번 경우]의 -(sum+최대)이거나 [2번 경우]의 -(sum)+최소가 되겠죠.

그리고 최댓값은 +방향으로 최대한 크게 만들어야 하는데 식 앞에 -가 있어 가장 작은 수를 만들어 -로 반전시키거나 해당 -의 영향은 작게 하고 큰 수를 더해야 하니 [1번 경우] -(sum+최소)이거나 [3번 경우] -(sum[0])+sum[1:]+최대가 됩니다.

 

식을 정리했으니 실제 값을 예로 "4-3+5-3+1+2-4"를 넣어보면 다음과 같습니다. (인덱스는 뒤에서부터입니다)

1. -를 만나기 전까지 sum을 계산하니 sum은 4가 됩니다.

1. 처음 -를 만난 경우는 -가 영향을 미치는 경우를 나눌 수 없으니 -(sum)+0으로 -4가 됩니다.

2. 다음 -를 만난 경우에 sum은 6(3+1+2)이고 최대 최소를 계산해보면

    최소 : -(6+(-4))=-2 또는 -(6)+(-4)=-10   -> -10

    최대 : -(6+(-4))=-2 또는 -(3)+(1+2)+(-4)=-4   -> -2

3. 다음 -를 만난 경우에 sum은 8(3+5)이고 최대 최소를 계산하면

    최소 : -(8+(-2))=-6 또는 -(8)+(-10)=-18   -> -18

    최대 : -(8+(-10))=2 또는 -(3)+5+-2=0   -> 2

4. 이후 식이 끝날 때까지 -가 없으니 sum값과 최댓값을 합한 4+2=6이 식의 최댓값이 됩니다.

 

Code

def solution(arr):
    minmax = [0, 0]
    sum_value = 0
    for idx in range(len(arr)-1, -1, -1):
        if arr[idx] == '+':
            continue
        elif arr[idx] == '-':
            tempmin, tempmax = minmax
            minmax[0] = min(-(sum_value + tempmax), -sum_value+tempmin)
            # -(sum + max):-가 식전체에 붙는 경우, -sum+min:-가 이전 -값 앞까지만 붙는 경우
            minus_v = int(arr[idx+1])
            minmax[1] = max(-(sum_value+tempmin), -minus_v+(sum_value-minus_v)+tempmax)
            # -(sum + min):-가 식전체에 붙는 경우, -v+(sum-v)+max:-가 바로 뒤의 값에만 붙는 경우
            sum_value = 0
        elif int(arr[idx]) >= 0:
            sum_value += int(arr[idx])
    minmax[1] += sum_value
    return minmax[1]

 

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

입출력 예

arr	result
["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]	3