프로그래머스 코딩테스트 - 스티커 모으기(2)

문제 설명

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

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

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

제약 사항

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

해결 방법

아이디어

첫 아이디어 - index를 짝홀로 나눠어 더하자!

홀수번째의 숫자를 모두 더하고 짝수 번쨰의 숫자를 모두 더해서 비교한다.

단순히 양옆의 스티커를 제거하지 못하고 건너뛰기 때문에 홀수와 짝수로 나눠 더하면 될 것 같았다. 더군다나 예제 문제가 하필 이 방식으로 풀려서 정답일 줄 알았다.

그러나 정답이 아니어서 혼란이 왔었다...

정답 아이디어 - DP를 활용하자!

다른 사람들의 질문을 보며 반례를 찾을 수 있었다.

 

[1,1,22,1,1,33]

이런 배열이 들어오게 된다면 첫 번째 아이디어로는 최대가 35가 된다. 하지만 실재로 최대는 55이 된다.

 

따라서 동적 계획법을 사용해서 스티커를 순회하며 연속하지 않게 스티커의 합을 구한 뒤 더 큰 값을 저장해주면 된다.

 

스티커 배열을 순회할 때 비교 대상은 (현재 스티커 + 전전스티커까지의 합)과 (전 스티커까지의 합)이다.

이때, 중요한 것은 시작을 첫 번째 스티커를 포함하는지 첫 번째 스티커를 포함하지 않는 지이다.

계산과정은 아래 그림과 같다.

알고리즘을 순서를 작성해보면

• 길이가 1인 경우 => 무조건 그 숫자가 최대가 됨
• 길이가 2인 경우 => 첫 번쨰 수와 두 번쨰 수를 비교해서 큰 값 반환
• 그 이상인 경우
  • dp0: 첫 번째 인자부터 시작
  • dp1: 두 번째 인자부터 시작
  • 나머지 스티커를 순회하며
    • 스티커 합 비교
  • 두 dp의 결과 비교

코드

function solution(sticker) {
    const length = sticker.length 
    const first = sticker.shift();
    
    if (length === 1) return first;
    
    const second = sticker.shift();
    
    if (length === 2) Math.max(first, second);
    
    const dp0 = [first, first]
    const dp1 = [0, second]

    sticker.forEach((s, i) => {
        if (i !== length - 3) {
            dp0[i + 2] = Math.max(dp0[i+1], dp0[i] + s)
        }
        dp1[i + 2] = Math.max(dp1[i+1], dp1[i] + s)
    })
    
    const max0 = dp0.pop();
    const max1 = dp1.pop();

    return Math.max(max0, max1);
}

결과