[프로그래머스] LV.3 스티커 모으기 (JS)

문제

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

입출력 예시

sticker	answer
[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

풀이

조건별로 분기하여 DP로 접근하여 풀 수 있는 문제이다. 먼저 DP로 접근해야 한다는 것을 파악하고, 2가지 경우를 따로 계산해주어야 한다는 것을 캐치한다면 손쉽게 풀 수 있다. (물론 모든 알고리즘 문제가 그렇듯 항상 접근 방법 캐치가 말처럼 쉬운 것은 아니다)

먼저 왜 DP로 접근이 가능한지, 그리고 DP를 가지고 어떻게 접근할 지 이야기 해보자.

문제의 규칙은 요약하면 다음과 같다. 스티커를 한장씩 뜯되 인접한 스티커는 뜯지 못할 때, 얻을 수 있는 최댓값을 구해야 한다. 일단 인접한 스티커라는 조건을 제쳐두고 생각하면, 누적합을 구하는 방식과 굉장히 유사하다는 것을 알 수 있다. 즉 현재 뜯은 스티커 + 다음에 뜯을 스티커의 누적합이 최댓값이 되는 경우를 찾아야 하는 것이다. 이는 이전에 구해놓은 값을 활용하는 형태가 되므로 중복 계산을 DP를 사용해 최적화 할 수 있을 것이다.

DP로 접근해야겠다고 생각했다면 또 다시 두개의 난관이 남아있다.

1. 첫 DP 배열을 어떻게 초기화 할 것 인가?
2. 점화식을 어떻게 세울 것 인가?

1번 부터 보자. 이 경우는 크게 어렵지 않다. 누적합을 구하는 것과 유사하기 때문에 우리는 처음에 스티커의 개수 만큼의 DP 배열을 모두 0으로 초기화해줄 수 있을 것이다. 즉 아래와 같다.

const dp = new Array(sticker.length).fill(0);

그렇다면 우리가 선언한 dp 배열은 다음과 같은 의미를 가질 것이다.

• dp[0] : 첫번째 스티커를 뜯었을 때까지의 누적합
• dp[1] : 두번째 스티커를 뜯었을 때까지의 누적합
• d[[2] : 세번째 스티커를 뜯었을 때까지의 누적합
• ...

그렇지만 문제 조건에 의해 누적합은 연달아서 구할 수가 없다. 왜냐하면 인접한 스티커는 뜯을 수 없다는 조건이 있기 때문이다. 게다가 주어진 배열은 일종의 Circular Buffer이기 때문에 배열의 첫과 끝이 서로 이어져 있는 형태로 생각해야 한다. 이 점을 유의하고 일단 점화식을 찾으러 가보자.

일단 첫 번째 스티커를 뜯었다고 생각해보자. 그렇다면 배열의 마지막 스티커와 첫 번째 다음에 있는 두 번째 스티커는 뜯을 수가 없다. 이는 위에서 언급했듯 주어진 배열이 Circular Buffer 형태이기 때문이다. 그렇다면 다음에 뜯을 수 있는 스티커는 최소 세 번째 스티커부터 가능하다. 세번째를 바로 뜯을 지, 아니면 네번째를 뜯을 지에 따라 반환되는 누적합이 다를 것이다.

다음으로는 첫 번째 스티커를 뜯지 않고 시작한다고 생각해보자. 그렇다면 처음으로 뜯을 수 있는 스티커는 최소 두 번째 스티커부터 시작하여 앞의 결과에 따라 마지막 스티커까지 뜯을 수 있을 것이다 (첫번째 스티커를 뜯지 않으므로 마지막 스티커는 위 경우와는 다르게 더 이상 인접한 스티커가 아니다). 즉 여기서 우리는 첫 번째 스티커를 어떻게 할 건지에 따라 2개의 분기로 나뉜다는 것을 알 수 있다.

일단 점화식에 다시 집중해보자. 위에서 우리는 인접한 스티커는 연달아 뗄 수 없기 때문에 최소 1칸 이상 건너뛰어야 한다는 것을 알 수 있었다. 즉 다음의 두 가지를 생각해볼 수 있다.

1. 앞서 스티커를 뜯은 경우, 현재 스티커는 뜯을 수 없다.
2. 앞서 스티커를 뜯지 않았다면 현재 스티커는 뜯을 수 있다.

그리고 1번과 2번을 실행했을 때 각각의 결과값이 있을 것이다. 우리가 필요한 것은 최댓값이기 때문에 1번과 2번 중에 최댓값을 계속 추출하면 된다. 따라서 위의 과정을 마지막까지 반복한다면 우리가 선언간 dp 배열의 마지막엔 최댓값이 들어있게 될 것이다. 말로 하면 이해가 잘 안 갈 수 있으니 바로 코드를 보자.

dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);

dp[i-1]의 의미는 현재 뜯어야 할 스티커가 i번째 일 때, 이미 이전의 스티커까지 뜯었을 때의 최댓값을 의미한다. 따라서 i번째 바로 직전의 스티커를 뜯었으므로 현재 i번째 스티커는 뜯을 수가 없다. 따라서 i번째의 최댓값은 당연히 이전의 최댓값과 동일하게 될 것이다.

반면 dp[i-2]의 경우는 한 칸 건너뛰어 그 이전의 스티커를 뜯었을때 까지의 최댓값을 의미한다. 즉 인접한 스티커가 아니기 때문에 현재 스티커 sticker[i]를 뜯을 수 있다. 따라서 이 둘의 합이 최댓값이 될 수 있는 수가 될 것이다.

이제 다시 앞으로 돌아가서 위에서 생각한 두 가지 경우를 생각해보자. 위의 점화식만으로는 정답을 얻을 수가 없다. 왜냐하면 첫 번째 스티커는 뜯을 수도 있고, 뜯지 않을 수도 있기 때문이다. 따라서 이 조건을 고려해주어야 한다.

이를 위해 두 개의 dp 배열을 선언해주자. dp1 은 1번째 스티커를 뜯는 dp배열을 말하고, dp2는 1번째 스티커를 뜯지 않았을 때의 dp배열을 의미한다. 이때 우리가 처음에 선언해준 DP 배열을 살짝 바꿔주어야 한다. 왜냐하면 위의 점화식에서 i-2의 값을 구해주는 것을 알 수 있다. 그런데 스티커의 크기와 동일하게 DP 배열을 만들어주면 첫 시작에 마이너스 값의 인덱스를 가리키게 되므로, 이를 막아주기 위해 sticker.length + 2의 크기를 가진 두 개의 DP 배열을 만들어 주자.

const len = sticker.length + 2;
const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);

// 만일 스티커가 하나밖에 없다면
// 첫번째 원소가 최댓값이므로 바로 리턴해주자.
if(sticker.length === 1) return sticker[0];

두 개의 DP 배열을 만들었다면 위에서 찾은 점화식을 적용할 수 있다. 이때 각각의 배열은 첫 스티커를 뜯는 경우와 그렇지 않은 경우로 분기한다는 것에 유의하자. 또한 기존에는 sticker[i]로 바로 현재 스티커의 값을 찾을 수 있었지만, DP 배열의 크기가 +2 되었으므로 해당 스티커 역시 sticker[i-2]로 찾아주어야 한다.

// 첫 스티커를 뜯는 경우
// 따라서 마지막 스티커는 뜯을 수 없으므로
// len-1 까지 반복해주어야 한다.
for(let i = 2; i < len-1; i++)
  dp1[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);

// 첫 스티커를 뜯지 않는 경우
// 따라서 마지막 스티커를 뜯을 수 있으므로
// len 까지 반복하고 i는 3부터 시작한다.
for(let i = 3; i < len; i++)
  dp2[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);

위 과정을 모두 수행하고 나면 dp1은 마지막 스티커를 떼지 않으므로 dp1[len-2] 위치에 최댓값이 있을 것이고 dp2는 마지막 스티커를 뗄 수 있으므로 dp2[len-1]에 최댓값이 담겨 있을 것이다. 따라서 두 값 중에 최댓값을 정답으로 리턴해주면 된다. 다음은 주석을 제외한 전체 코드이다.

코드

function solution(sticker) {
  const len = sticker.length + 2;
  const dp1 = new Array(len).fill(0);
  const dp2 = new Array(len).fill(0);
  
  if(sticker.length === 1) return sticker[0];
  
  for(let i = 2; i < len-1; i++)
    dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2]);
  
  for(let i = 3; i < len; i++) 
    dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i-2]);
  
  return Math.max(dp1[len-2], dp2[len-1]);
}

출처

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