프로그래머스 LEVEL 3(스티커 모으기(2))

사용 언어 : javascript
해결 날짜 : 2022-11-30
해결 방법 :
- sticker가 하나인 경우 그 값을 반환
- sticker가 두 개인 경우 둘 중 큰 값을 반환
- 그 외의 경우
  - sticker가 원형으로 처음과 끝이 이어져 있으므로, 두 개의 dp로 나눠서 해결
    - 1번 dp: sticker의 0번 인덱스를 고려하는 경우
      - 마지막 스티커는 선택 불가능
      - sticker의 마지막 인덱스를 제외한 나머지로 초기화
    - 2번 dp: sticker의 1번 인덱스를 고려하는 경우
      - 처음 스티커는 선택 불가능
      - sticker의 처음 인덱스를 제외한 나머지로 초기화
  - 두 dp는 길이가 똑같고, 첫 인덱스(1번 인덱스)는 0번, 1번 인덱스 중 큰 값
  - 그 이후 인덱스는 dp[i] + dp[i - 2], dp[i - 1] 중 큰 값으로 update
  - 두 dp의 최대값(마지막 인덱스)를 비교하여 둘 중 큰 값을 반환
회고 :
- 처음에 두 dp에 대한 반복문을 따로 작성해서 통일하는 과정에 1번 테스트 케이스가 실패했다.
- 생각해보니 sticker의 길이가 2인 경우, dp[1]에 대한 업데이트를 수행할 수 없기 때문에 실패했던 것 같다.
- 엣지 케이스 잘 생각하기

코드

function solution(sticker) {
    if (sticker.length === 1) return sticker[0];
    else if (sticker.length === 2) return Math.max(...sticker);
        
    const dp_1 = sticker.slice(0, -1),
          dp_2 = sticker.slice(1);
        
    dp_1[1] = Math.max(dp_1[0], dp_1[1]);
    dp_2[1] = Math.max(dp_2[0], dp_2[1]);
        
    for (let i = 2; i < dp_1.length; i++) {
        dp_1[i] = Math.max(dp_1[i] + dp_1[i - 2], dp_1[i - 1]);
        dp_2[i] = Math.max(dp_2[i] + dp_2[i - 2], dp_2[i - 1]);
    }
        

    return Math.max(dp_1[dp_1.length - 1], dp_2[dp_2.length - 1]);
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges