[프로그래머스 lev3/JS] 스티커 모으기(2)

문제 출처

프로그래머스 lev3 - 스티커 모으기(2)

나의 풀이 (실패)

이분탐색으로 풀려고 했다.
하지만 isTrue 함수를 통해 mid 값을 만족하는 원소들을 찾기 위해 dfs를 돌리는 과정에서 막혔다. dfs 재귀의 경우 for문에서 무조건 let i=0으로 잡으면, 이미 지나친 원소들을 다시 고려하는 문제가 생겨서 prevIdx로 index를 추적하려 했으나, 어디서 초기화를 해야할지가 막막했다.

dfs 부분에서는 전부 탐색하는 게 아니라 만족하는 경우의 수 하나라도 찾으면 바로 끝내도록 했으나, 그래도 시간초과는 못 막을 것 같기도 하다..

function solution(sticker) {

  function isTrue(arr, targetNum){
    // 요소 합이 target을 만족하면서 문제 조건 만족하는 원소 조합이 있는지 판단 
    let tmp = []
    let ch = Array.from({length: arr.length}, () => 0)
    let flag = false

    // 재귀 시 index = 0 부터 다시 탐색하기 때문에 여러 조합이 순서만 바뀐 채 중복해서 등장한다.
    // 예를 들어, arr[0], arr[2] 를 가져다 썼으면 arr[3]부터 돌아야 하는데 
    // 재귀는 복귀에서 index=0부터 시작하기 때문에 arr[1]를 고려할 가능성이 생긴다. 
    // let i=prevIdx;로 시작하면 어디서 다시 초기화해줘야 하는지가 어렵다. 
    const dfs = (sum = 0, prevIdx) => {
      if(flag) return 
      if(sum > targetNum) return 
      if(sum === targetNum) {
        console.log(tmp, ch)
        // flag = true
        // return 
      }

      for(let i=prevIdx; i<arr.length; i++){
        if(!tmp.includes(arr[i]) && ch[i] === 0){
          // 이 로직으로는 check 배열이 제대로 체크되지 않는다. 
          ch[i-1 ? arr.length-1 : i-1] = 1
          ch[i] = 1
          ch[i+1 === arr.length ? 0 : i+1] = 1
          // console.log(arr[i])
          tmp.push(arr[i])
          dfs(sum + arr[i], i >= arr.length-1 ? 0 : i) // 여기서 prevIdx를 초기화해버리면 여전히 중복이 발생한다..
          tmp.pop()

          ch[i-1 ? arr.length-1 : i-1] = 0
          ch[i] = 0
          ch[i+1 === arr.length ? 0 : i+1] = 0
        }
      }
    }
    dfs()
    return flag
  }
  isTrue(sticker, 36) // 여기서 테스트해보려 했으나 37도 true가 나와서 막혔다..
  
  let min = Math.min(...sticker)
  let max = sticker.reduce((a,b) => a+b, 0)
  console.log(min, max)
  while(min <= max){
    const mid = (min + max) / 2 >> 0

    if(isTrue(sticker, mid)) min = mid - 1
    else max = mid + 1 
  }
  return min
}

console.log(solution([14, 6, 5, 11, 3, 9, 2, 10]))
// console.log(solution([1, 3, 2, 5, 4]))

다른 풀이

dp는 어렵다.

누적합을 구해야 하는 문제라면? => 이렇게 이전에 찾은 값을 활용해야 하는 구조라면 DP를 고려하는 게 좋다(중복 방지).

문제를 풀 때 고려해야 할 것은 2가지다.
1. 각 배열에서 스티커를 떼는 경우의 수
2. 첫번째 스티커와 마지막 스티커가 공존할 수 없다는 것.

1. 각 배열에서 스티커를 떼는 경우의 수
스티커를 떼는 경우는 다음과 같다.

• 앞에서 스티커를 떼면, 현재 스티커를 뗄 수 없다.
• 앞에서 스티커를 떼지 않았다면, 현재 스티커를 뗄 수 있다.

최대값을 구하는 것이므로, 현재 sticker[i]에서의 최대값은 dp[i] = sticker[i] + max(dp[i-2], dp[i-3])과 같다.

• [..., dp[i-3], dp[i-2], dp[i-1], dp[i], ...]에서 i-2과 i를 선택하거나
• [..., dp[i-3], dp[i-2], dp[i-1], dp[i], ...]에서 i-3과 i를 선택하거나

2. 첫번째 스티커와 마지막 스티커는 공존할 수 없다.
dp 배열을 2개로 나눈다. 첫번째 스티커를 선택하는 경우의 배열과 첫번째 스티커를 선택하지 않는 경우의 배열.

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])
}

참고

[프로그래머스] 스티커 모으기(2) / Java