[HackerRank] Candies

Candies | HackerRank

---

  학생들에게 사탕을 1개 이상씩 나눠줄 때 필요한 사탕의 최소 갯수를 구하는 문제이다. 단, 서로 이웃해있는 두 학생들 중 점수가 높은 아이는 더 많은 사탕을 주어야한다. 또한 점수가 같은 경우 반드시 사탕을 같은 갯수로 줄 필요가 없다. 즉, 학생들의 점수가 [1, 2, 2] 라면, 사탕은 [1, 2, 1] 개를 주어야 사탕의 최소 갯수가 된다.

 

1. 문제 분석

문제 1

  주어진 예시를 한 번 풀어보자. 단순하게 생각하면 i번째 학생은 i - 1 번째 학생보다 점수가 높으면 i -1 번째 학생보다 +1개를 갖고, 점수가 낮으면 -1개를 가질 것이다. 이 방식으로 사탕을 준다면 A1 처럼 된다. 그런데 문제는 사탕의 최소 갯수를 구해야 하기 때문에 A2와 같이 낮은 점수를 가진 학생보다 -1 하는 것이 아닌, 1로 바꿔버려야 답이 될 수 있다.

 

문제 2 - 0부터 나눠주기

  그렇다면 문제 1에서 학생 수가 2명 더 추가되었을 때에도 같은 방식으로 풀 수 있을까? 위 방식으로 풀면 추가된 학생들은 사탕을 0개 이하로 갖게되어 답의 조건(1개 이상씩 나눠주기)을 만족하지 못하게 된다.

 

  추가된 학생들도 1개 이상 주기 위해서는 4번 학생(6점)에게 최소 4개를 주었어야 한다. 왜냐하면 6부터 연속되는 내림차순인 숫자가 총 4개가 있기 때문이다. 즉, 0번 부터 차례로 사탕을 줄 때 내림차순이 포함된 경우 어느위치에서 내림차순 발생하고, 내림차순에 포함된 학생들이 총 몇 명인지를 확인하여야한다.

 

문제 2 - n부터 나눠주기

  0부터 시작했을 때 내림차순이라는 것은 마지막(n)부터 나눠준다면 오름차순이 되지 않을까? 그래서 이번엔 마지막부터 사탕을 나눠주었다. 결과 원래 방향에서 잘못된 부분은 잘 맞았지만, 반대로 원래방향에서 잘 나눠주었던 부분은 틀린 답안이 나왔다. 그렇다면 이 둘을 적절히 조합한다면 답을 찾을 수 있지 않을까?

 

문제 2 - 두 방향을 합치면 정답!

  각 학생들은 이제 2가지의 사탕 갯수 후보들을 갖게 되었다. 이 중 어떤 것을 선택할지 기준만 잘 세우면 문제는 해결될 것이다. 잘 생각해보면 내림차순의 문제는 원래 가져야하는 숫자보다 더 적은 숫자를 갖게되어 어디선가 0 미만의 사탕 수를 만들어 버리는 것이다. 즉, 어느 방향에서 만든 잘못된 내림차순은 원래 답보다 더 작은 숫자를 갖게 된다. 따라서 두 방향의 숫자들 중 더 큰 수를 취한다면 답이 된다.

 

2. 코드

function candies(n, arr) {
  if (n === 1) return 1;
  const dp1 = Array(n).fill(0);
  dp1[0] = 1

  const dp2 = Array(n).fill(0);
  dp2[n - 1] = 1;

  for (let i = 1; i < n; i++) {
    if (arr[i - 1] >= arr[i]) dp1[i] = 1;
    else dp1[i] = dp1[i - 1] + 1;
  }

  for (let i = n - 2; i >= 0; i--) {
    if (arr[i + 1] >= arr[i]) dp2[i] = 1;
    else dp2[i] = dp2[i + 1] + 1;
  }

  let cnt = 0;
  for (let i = 0; i < n; i++) {
    cnt += Math.max(dp1[i], dp2[i]);
  }
  return cnt;
}