[프로그래머스] LV.4 사칙연산

문제

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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

풀이

이전에 풀었던 동일 레벨 난이도의 다른 문제와 비슷한 류의 문제이다. 최적의 행렬 곱셈 문제와 비슷한 로직이 요구되는 것을 차후 풀이를 읽고 나면 이해할 수 있을 것이다. 해당 문제 풀이를 보고나서 시간이 된다면 해당 포스트 역시 참고해보자.

1) 결합법칙

문제에 조건에서 주어지는 연산자는 더하기와 빼기이다. 이때 더하기는 결합법칙이 성립하지만, 빼기의 경우에는 성립하지 않는다. 이것이 시사하는 바는 빼기의 경우 어떤 순서로 계산하느냐에 따라 최종 결과값이 달라질 수 있다는 점이다. 이때 문제에서 요구하는 답은 계산 결과의 최댓값이다. 단순무식하게 생각한다면 모든 경우의 수를 일일이 계산해서 그 중에서 최대값을 도출하는 방법이 있을 수 있다. 하지만 이 방법은 당연히 시간이 많이 소요되는 작업이고, 그로인해 효율성 테스트를 통과할 수 없을 것이다. 만약 4개의 피연산자가 있다 하더라도 4C2 x 3C2 = 18가지의 경우의 수가 생기는데, 최대 피연산자의 개수가 101개 이기 때문에, 101C2 x 100C2 x 99C2 x ... x 3C2 의 경우의 수를 고려하기에는 시간이 매우 부족할 것이다.

그렇지만 모든 경우의 수를 일일이 계산하다 보면 몇개의 경우들에서는 동일한 값이 나오는 것을 확인할 수 있다. 이는 연산자가 덧셈과 뺄셈이 섞여 있기 때문인데, 앞에서 설명한 바와 같이 덧셈의 경우엔 순서에 상관을 받지 않기 때문이다. 따라서 동일하게 계산된 뺄셈 순서를 공유하는 경우라면 모두 동일한 최종 결과값을 가지게 된다. 중복되는 경우가 생긴다면 굳이 이를 일일이 계산할 필요 없이 중복을 제거해 효율성을 높일 수 있을 것이다. 다음 과정에서 어떤 방법으로 중복을 제거할 수 있을지 살펴보자.

2) 범위계산

다음과 같은 식이 존재한다고 가정해보자.

• O1 + O2 - O3 - O4 + O5 - O6

우리가 최종적으로 구해야 할 값은 마지막으로 계산된 값 중에서의 최댓값이다. 이때 덧셈과 뺄셈의 계산은 항상 2개의 피연산자와 하나의 연산자의 구성으로 이루어진다는 것을 알 수 있다. 즉 하나의 연산을 수행하기 위해서는 O1 + O2 처럼 각각 3개의 개별 요소가 필요하다. 그리고 이에 대한 결과값은 또 다른 하나의 피연산자로 변환되고, 다른 피연산자와 계속해서 연산이 가능하다.

이때 하나의 피연산자에 주목해보자. 각각의 피연산자는 단독으로 존재할 때는 덧셈과 뺄셈이 불가능하다. 즉 자신의 고유한 값으로 존재할 수 밖에 없다. 아무런 변형이 이루어지지 않은 처음 선언된 그 상태의 값을 유지하는 것이다. 우리는 해당 상태를 하나의 최댓값으로 두고 연산을 진행할 수 있다.

이것이 무슨 말인지 자세히 들여다보자. 연산이 일어나는 순서대로 묶는 것은 너무 많은 경우의 수가 발생하고, 또 중복되는 경우를 모두 포함한다. 때문에 일일이 이들의 순서를 지정하는 것은 매우 비효율적인 작업이다. 하지만 각각의 피연산자 하나가 초기 최대값으로 존재할 수 있다면 다음의 가정을 펼칠 수 있다.

• 초기 최대값을 상정하면, 이를 이용해 범위를 하나씩 늘려가면서 최대값을 갱신할 수 있다.

직접 예시를 통해 무슨 말인지 살펴보자. 우리는 위에서 어떤 연산이 일어나면 반환되는 값은 하나의 피연산자가 되는 것을 확인할 수 있었다. 따라서 연산자가 아무리 많더라도 연산의 조건을 충족한다면 최종적으로 반환되는 값은 단 하나의 피연산자(= 결과값)이 될 것이다. 따라서 다음이 성립한다.

1. O1 + [O2 ~ O6] : O1과 O2 ~ O6 까지 연산의 결과의 합
2. [O1 ~ O2] - [O3 ~ O6] : O1 ~ O2 까지 연산의 결과와 O3 ~ O6 까지 연산 결과의 차
3. [O1 ~ O3] - [O4 ~ O6] : O1 ~ O3 까지 연산의 결과와 O4 ~ O6 까지 연산 결과의 차
4. [O1 ~ O4] + [O5 ~ O6] : O1 ~ O4 까지 연산의 결과와 O5 ~ O6 까지 연산 결과의 합
5. [O1 ~ O5] - O6 : O1 ~ O5 까지 연산의 결과와 O6의 차

즉 다음과 같은 5가지 형태의 결과값을 얻을 수 있고, 이 중에서 가장 큰 값을 구한다면 중복되는 요소를 제거해 효율적으로 최댓값을 도출할 수 있다.

위의 경우엔 6개의 피연산자가 있었고, 그로인해 5가지의 형태가 도출됨을 확인할 수 있다. 즉 N개의 피연산자가 있다면 N-1개의 범위 결합 형태로 묶을 수 있다는 것이다. 이외의 범위 결합 형태는 불가능한데, 왜냐하면 결합법칙의 특성상 인접한 피연산자들끼리 묶이는 것이 우선되기 때문이다.

이 같은 형태를 들여다보면, 이전에 구한 값을 활용해 하나씩 범위를 늘여가며 값을 갱신하고 있기 때문에 DP 알고리즘과 그 궤를 같이하고 있음을 알 수 있다. 따라서 우리는 해당 문제를 풀기위해 DP 알고리즘을 적용해볼 것이다.

3) DP 알고리즘

먼저 사용할 DP 배열 먼저 정의를 해보자. 범위를 통해 접근하기 때문에 다음과 같이 선언할 수 있다.

• DP[i][j] : i번째 피연산자부터 j번째 피연산자까지 연산의 최대값

이때 한 가지 주의해야 할 점은, 연산이 덧셈과 뺄셈으로 구분된다는 점이다. 덧셈의 경우에는 가장 큰 수끼리 합하는 것이 최대값을 만들지만, 뺄셈의 경우에는 최대값을 구하는 법이 약간 다르다. 뺄셈은 가장 큰 값에서 가장 작은 값을 빼는 경우가 최대값을 만들기 때문에, 우리는 연산자의 종류에 따라 로직을 분리할 필요가 있다.

로직 분리 뿐만 아니라, 최대값을 만드는데 있어 가장 큰 값과 가장 작은 값도 요구하고 있는 것을 알 수 있다. 이때 각각의 경우는 모두 연산의 결과로 도출되는 값일 것이다. 즉 똑같이 DP 알고리즘에 의해 구해지는 값이 될 것이다. 따라서 우리는 이에 대한 각각의 DP 배열을 만들어 줄 것이다.

• MAX_DP[i][j] : i번째 피연산자부터 j번째 피연산자까지 최대값
• MIN_DP[i][j] : i번째 피연산자부터 j번째 피연산자까지 최소값

그리고 이들은 덧셈이냐 뺄셈이냐에 따라서 저장되는 값이 서로 다를 것이다. 앞서 살펴본 것처럼 로직을 분리해서 각 DP 배열에 값을 갱신해야 한다. 이때 최대/최소값을 비교하는 대상은 항상 자기자신(=DP[i[j])가 된다는 점을 유의하자. 서로 다른 두 범위의 연산 결과가 더 크거나 작을수도 있지만, 그 결과가 기존값보다 오히려 작거나 클수도 있기 때문이다. 예를 들어 최대값 DP 배열의 경우엔 다음의 점화식이 성립한다.

• 덧셈인 경우

  • max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][new] + max_dp[new+1][j])
    

• 뺄셈인 경우

  • max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][new] - min_dp[new+1][j])

범위를 설정해 연산이 일어나더라도 항상 두 개의 범위와 하나의 연산자가 충족되어야 한다. 따라서 max_dp[i][j]는 i부터 j까지 연산의 최댓값을 담고 있지만, 해당 결과는 위에서 본 경우의 수 처럼 두 가지 범위로 분할되어 계산이 가능하다. 이는 순차적인 구조를 띄기 때문에 연산 순서에 따라 달라지는 결과값을 모두 고려해서 최대값을 계산할 수 있다. 이때 뺄셈의 경우에서는 max_dp - min_dp 를 통해 최대값을 구하는 것에 유의하자.

반면 최소값 DP 배열이라면 다음의 점화식을 구할 수 있다.

• 덧셈인 경우

  • min_dp[i][j] = Math.max(min_dp[i][j], max_dp[i][new] + min_dp[new+1][j])
    

• 뺄셈인 경우

  • min_dp[i][j] = Math.max(min_dp[i][j], max_dp[i][new] - max_dp[new+1][j])

최대값 DP 배열의 점화식과 유사하지만, 최소값을 구하는 방법만 다를뿐이다. 뺄셈의 경우 min_dp - max_dp를 통해 최소값을 구하고 있다. 각각의 경우 왜 다른 방식이 적용되는지는 조금만 생각해본다면 쉽게 이해할 수 있을 것이다.

4) DP 알고리즘 구현

점화식까지 모두 찾았으니 직접 DP 알고리즘을 구현해 문제를 풀어보도록 하자. 누누이 강조하는 사항이지만 점화식 만큼이나 중요한 것이 초기 DP 배열의 정의이다. 우리는 두 가지 DP 배열을 쓰기 때문에 2개의 DP 배열을 초기화 해주어야 한다.

문제에서 주어지는 arr 배열에는 피연산자와 연산자가 혼합되어 들어있다. 문제 조건에 의해 식이 성립하지 않는 경우는 존재하지 않기 때문에 항상 피연산자의 개수 - 1 = 연산자 를 만족함을 알 수 있다. 이 관계를 이용해 우리는 DP 배열에 피연산자만 담도록 하자. 어떤 값을 사용해도 상관없지만 피연산자의 개수를 통해 DP 배열을 초기화하고 관리하도록 하겠다. 피연산자-연산자 관계를 통해 연산자 개수를 통해 초기화를 해도 상관 없다.

이때 초기값은 최대값 DP 배열의 경우엔 -Infinity로, 최소값 DP 배열의 경우엔 Infinity로 하도록 하자. 이는 연산의 결과로 나올 수 있는 최대/최소값이 음수일 수도 있기 때문에, 해당 경우까지 모두 고려하여 최대 또는 최소값을 비교할 수 있어야 하기 때문이다. 최대값의 경우엔 더 작은 경우 갱신이 일어나기에 항상 가장 작은 값으로 간주되는 -Infinity를, 최소값은 더 큰 경우 갱신이 일어나므로 항상 가장 큰 값으로 간주되는 Infinity를 할당한다.

// 피연산자의 개수는 arr배열(= 피연산자+연산자 개수)을 통해 구할 수 있다
// arr의 길이는 항상 홀수를 만족하기 때문에
// arr을 2로 나눈 값을 올림하면 항상 피연산자의 개수가 된다
const operandsCount = Math.ceil(arr.length / 2);

// 최대값 dp와 최소값 dp를 생성
// 초기화는 각각 -Infinity와 Infinity로 진행
const max_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(-Infinity));
const min_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(Infinity));

그리고 위에서 우리는 각각의 피연산자는 그 자체로 최대값으로 간주하고 연산을 진행할 수 있음을 살펴보았다. 따라서 각 DP배열에 피연산자가 속하는 위치에 피연산자의 값을 넣어주도록 하자. 이때 우리는 DP 배열에 피연산자만을 다루기 때문에 본래 배열인 arr에서 연산자의 위치까지 고려해서 값을 가지고 와야하는 것에 주의하자. 또한 arr 배열에 들어있는 모든 피연산자의 타입은 문자열이기 때문에 추후 연산을 위해 이를 숫자형(Number)으로 변환 후에 넣어주도록 하자.

for(let i = 0; i < operandsCount; i++) {
  // 연산자까지 고려한 각 피연산자의 값(= i*2)
  // 문자열을 숫자형으로 변환
  max_dp[i][i] = +arr[i*2];
  min_dp[i][i] = +arr[i*2];
}

DP 배열의 초기화가 끝났으니 위에서 찾은 점화식을 그대로 구현해주면 된다. 이때 우리는 피연산자의 개수가 N일때 총 N-1개의 타입이 존재할 수 있음을 확인했다. 따라서 가장 외부에서 순회하는 반복문은 N-1번의 반복만 돌면 된다. 또한 arr 배열을 통해 연산자를 가져올 때엔 항상 올바른 인덱스값을 적용해주어야 하는 것에 주의하자. 우리는 반복문 내부에서 피연산자만을 다루기 때문에, 연산자에 접근하기 위해서는 arr에 접근해야 하고 더불어 사용하는 인덱스 값의 조정도 필요하다.

// N-1 만큼 반복문을 순회하며 최대값 탐색
for(let cnt = 1; cnt < operandsCount; cnt++) {
  for(let i = 0; i < operandsCount - cnt; i++) {
    let j = i + cnt;
    for(let k = i; k < j; k++) {
      // 연산자의 위치를 구하는 인덱스 값에 주의
      if(arr[k*2+1] === '+') {
        max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]);
        min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]);
      } else {
        max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]);
        min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]);    
      }
    }
  }
}

모든 계산이 끝나면, 우리가 처음에 선언했던 DP 배열의 정의에 따라 max_dp[0][마지막 피연산자 위치]에 최대값이 들어있게 될 것이다.

return max_dp[0][operandsCount-1];

5) 전체코드

앞서 링크를 건 포스트와 상당 부분 유사한 문제이다. 물론 분기점이 생기고 두 개의 DP 배열을 사용하는 점에서 차이가 분명히 있지만, 내부적으로 DP 알고리즘을 적용하는 부분에 있어서는 동일한 로직을 사용하고 있다. 이는 두 문제 모두 범위로 접근할 수 있기 때문이다. 따라서 해당 포스트에서 대부분 상세한 설명은 이전 포스트와 겹치는 부분이 많아 핵심 위주로 진행했다. 만약 갑자기 이해가 안 가는 부분이 있다면 이전 포스트를 확인해보며 같이 읽어보는 것도 좋을 듯 하다. 주석을 제외한 전체코드는 다음과 같다.

function solution (arr) {
  const operandsCount = Math.ceil(arr.length / 2);
  const max_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(-Infinity));
  const min_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(Infinity));
  
  for(let i = 0; i < operandsCount; i++) {
    max_dp[i][i] = +arr[i*2];
    min_dp[i][i] = +arr[i*2];
  }
  
  for(let cnt = 1; cnt < operandsCount; cnt++) {
    for(let i = 0; i < operandsCount - cnt; i++) {
      const j = i + cnt;
      for(let k = i; k < j; k++) {
        if (arr[k*2+1] === '+') {
          max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]);
          min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]);
        } else {
          max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]);
          min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]);
        }
      }
    }
  }
  
  return max_dp[0][operandsCount-1];
}

출처

https://programmers.co.kr/learn/courses/30/lessons/1843