[CodeKata] 프로그래머스(Lv3) : 스티커 모으기(2)

🥋 Oooth More!! (Level 3) 

 

 

🧮 풀이

먼저, sticker 배열의 홀수 요소들만의 합(oSum), 짝수 요소들만의 합(eSum) 중 최대값을 max에 저장했다.

그리고, 2가지 출발점(s1 = 최대값, s2 = 최대값의 인접값 중 큰 값) 부터 1칸을 건너뛰고 두 번째, 세 번째 중 최대값을 누적하면서 스티커를 뜯은 값과 최대값(max)를 비교해 큰 값을 저장했다.

 

이처럼 풀이했을 때, 예외 케이스가 발생할 수 있는 방법이었기에 정확성도 50% 미만이고, 반복적인 순회로 효율성을 통과하지 못했다.

function solution(sticker) {
  let oSum = 0, eSum = 0;
  for (let i in sticker) {
    if (+i % 2 === 0) {
      eSum += sticker[i]
    }
    else {
      oSum += sticker[i]
    }
  }

  let max = Math.max(oSum, eSum);
  
  const e = sticker.length-1
  const s1 = sticker.indexOf(Math.max(...sticker))
  const s2 = sticker.indexOf(Math.max((sticker[s1-1] ?? sticker[e]), (sticker[s1+1] ?? sticker[0])))
  
  for (let s of [s1,s2]) {
    let arr = [...sticker];
    arr = [...arr.splice(s-1 < 0 ? e : s-1), ...arr.splice(0,(s-1 < 0 ? e : s-1))]

    let i = 1;
    let nowMax = 0;
    while (i <= e) {
      nowMax += arr[i];
      i = arr[i+2] < arr[i+3] ? i+3 : i+2
    }
    
    max = Math.max(max, nowMax)
  }
  
  return max
}

 

 

🖇 리뷰

모범답안을 보니 생각보다 풀이는 간단했다.

 

하지만 DP(Dynamic Programming)을 통해 특정 인덱스에서 가질 수 있는 최대 누적값을 저장해나가는 방법,

그리고 이를 첫 번째 스티커를 뜯는 경우 / 안뜯는 경우 2가지를 고려해서 순회한다는 아이디어를 발상하는 초기과정이 매우 어려웠을 것이다.

* DP(Dynamic Programming) 참고링크 : https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP  

 

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://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EC%8A%A4%ED%8B%B0%EC%BB%A4-%EB%AA%A8%EC%9C%BC%EA%B8%B0-JS  

 

• 먼저 len 길이를 설정해준다. DP를 실행할 때, 현재 인덱스의 전값, 전전값 을 확인하므로 i = 2를 시작점으로 잡기 위해 sticker.length에 2를 더해준 것이다.
• dp1, dp2 는 각각 DP를 실행하기 위한 배열로 0으로 초기화한다. 각각 첫 번째 스티커를 뜯는 / 뜯지 않는 경우에 해당한다.
• sticker가 1개인 경우, sticker[0] 만 뜯을 수 있으므로 이를 반환한다.
• 먼저, 첫 번째 스티커를 뜯는 경우(dp1)을 연산한다. dp1[2]가 sticker[0]을 뜯는 경우에 해당하며, 이 경우는 마지막 스티커를 뜯지 못하기 때문에 i가 len-1 미만까지만 확인한다.
• DP는 현재 차례가, 1) 이전 스티커를 뜯어 현재는 뜯지 않는 경우, 2) 전전 스티커까지 뜯어 현재까지 뜯는 경우, 중 최대값을 계산한다.
• 마찬가지로, 첫 번째 스티커를 뜯지 않는 경우(dp2)를 연산한다. 이 땐 마지막 스티커를 뜯을 수 있어서 i가 len 미만까지 확인한다.
• dp1, dp2의 끝값이 첫 번째 스티커를 뜯는 / 뜯지 않는 각각의 경우에 대한 최대값에 해당한다. 이 중, 큰 값을 최종 반환한다.

 

동적 프로그래밍의 원리 자체는 어렵지 않다. 전과 전전의 연산값을 참고해, 현재의 연산값을 누적해나가는 방법이다. (ex) 피보나치 수열)

 

하지만, 이 문제의 경우, 첫 번째 스티커를 뜯는지 여부에 따라 2가지 연산을 해야 한다는 점, 그리고 여기에 따라 어디까지 탐색을 하는지(len) 설정하는 과정 등이 매우 어려운 문제였다!