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

function solution(sticker) {
  const n = sticker.length;
  if (n === 1) {
    return sticker[0];
  }

  let f = sticker[0];
  let s = sticker[0];
  let curr = 0;
  for (let i = 2; i < n - 1; i++) {
    curr = Math.max(f + sticker[i], s);
    f = s;
    s = curr;
  }
  const result1 = s;

  f = 0;
  s = sticker[1];
  curr = 0;
  for (let i = 2; i < n; i++) {
    curr = Math.max(f + sticker[i], s);
    f = s;
    s = curr;
  }

  return Math.max(result1, s)
}

---

문제 해석

우선 문제를 처음 보면 많은 풀이법이 생각난다.
DFS/BFS를 통해 완전 탐색을 하며 최댓값을 도출하는 방법, deque를 통해 rotate시키며 해결하는 방법.
하지만 JavaScript로 풀기에 배열을 계속해서 사용하는 것은 효율성 측면에서 옳지 않기에 DP로 푸는 방법을 오랫동안 고민했습니다.

언뜻 모든 인덱스를 시작점으로 하는 방법을 모두 계산해야하나 싶지만 0번째 인덱스, 1번째 인덱스에서 시작하는 것만 하면 나머지는 모두 겹치게 됩니다.

따라서 0번째 인덱스, 1번째 인덱스에서 시작하는 것만 DP로 구현한 뒤 2개의 값을 비교해 최댓값을 도출하면 됩니다!

---

풀이 방향

1. 2개의 변수를 가지고 가며 계산 결과를 업데이트 시켜줍니다.

위의 코드에서는 f 와 s 로 변수 선언을 해주었습니다. sticker의 값을 for문으로 선회하며 f를 s로, s를 계산한 값으로 업데이트 합니다.

예를 들어 f = 14, s = 15이고 처음 계산한 값이 18이면 그 다음은 f = 15, s = 18이 됩니다.

2. 우선 0번째 인덱스의 경우와 1번째 인덱스의 경우 초기값 설정이 살짝 다름을 유념합시다.

0번째 인덱스의 경우 f = sticker[0], s = sticker[0]으로 설정해야합니다.
1번째 인덱스의 경우 f = 0, s = sticker[1]로 설정해야합니다.

3. 마지막으로 두 값을 비교하여 최댓값을 최종 정답으로 반환합니다.

---

처음에는 for문 내에서 새로운 값에 해당하는 'curr'변수를 for문 스코프 내의 변수로써 두번 선언은 해주는 방식으로 작성하였습니다.
->

  let f = sticker[0];
  let s = sticker[0];
  for (let i = 2; i < n - 1; i++) {
    let curr = Math.max(f + sticker[i], s);
    f = s;
    s = curr;
  }
  const result1 = s;
  console.log(s);

  f = 0;
  s = sticker[1];
  for (let i = 2; i < n; i++) {
    let curr = Math.max(f + sticker[i], s);
    f = s;
    s = curr;
  }

하지만 이렇게 하니 효율성 부분 3번 케이스에서 시간초과가 나왔습니다.

DP방법으로 했기에 알고리즘 자체가 틀린것은 아닌것 같아 최대한 선언을 줄이는 방향으로 진행하기 위해 최상단의 정답 코드와 같이 curr이라는 변수를 전역 스코프에서 let으로 먼저 선언한 뒤 계속 재할당하는 방법을 사용하였더니 시간초과에 걸리지 않았습니다.