LeetCode - Candy (Javascript)

문제 설명

줄을 선 아이들의 평가(별점?)점수에 따라 최소 한 개의 사탕을 배분해야 한다.
더 높은 평가점수를 가진 아이는 양 옆의 아이들보다 더 많은 사탕을 받아야 한다.

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

---

소스 코드 (첫 시도)

통과가 되긴 했는데…
역시나 첫 시도는 시간복잡도 측면에서 처참한 결과가 나왔다 ㅜ

내가 여기서 짠 로직은, 처음에는 우측 방향으로 한 번 순회를 하고 → 다시 반대 방향으로 순회를 하는 방식이다.

function candy(ratings) {
  let answer = [];
  if (ratings.length === 1) return 1;
  for (let i = 0; i < ratings.length; i++) {
    if (ratings[i - 1] < ratings[i]) answer[i] = answer[i - 1] + 1;
    else answer[i] = 1;
  }
  for (let i = ratings.length - 1; i >= 0; i--) {
    if (ratings[i + 1] < ratings[i] && answer[i + 1] >= answer[i]) {
      answer[i] = answer[i + 1] + 1;
    }
  }
  return answer.reduce((prev, cur) => prev + cur);
}

---

소스 코드 (최종)

로직을 바꾸지는 않았고, 활용한 자료구조와 조건문의 시작점을 살짝 바꿔줬다.

우선, 가장 첫 번째로, 1회차에 사탕을 건내준 횟수가 담긴 배열에서 순서를 서로 바꿔줘야 할 필요는 없었다. 따라서 object를 사용하며 조금 더 탐색과 값의 변경에 있어 효율성 증진을 시도했다. (answer =[] → distributed = {})

그리고 추가적으로 두 번째 순회에서 굳이 끝에서 시작할 필요가 없었다. 첫 번째 순회에서는 모든 배열의 변화를 줘야하지만, 두 번째 순회는 끝 요소의 경우는 체크가 불필요하다.

function candy(ratings) {
  const distributed = {};
  let sum = 0;
  if (ratings.length === 1) return 1;
  for (let i = 0; i < ratings.length; i++) {
    if (ratings[i - 1] < ratings[i]) distributed[i] = distributed[i - 1] + 1;
    else distributed[i] = 1;
  }
  for (let i = ratings.length - 2; i >= 0; i--) {
    if (ratings[i + 1] < ratings[i] && distributed[i + 1] >= distributed[i]) {
      distributed[i] = distributed[i + 1] + 1;
    }
  }
  Object.values(distributed).forEach((num) => (sum += num));
  return sum;
}

이렇게 조금의 수정을 해줬는데 시간 효율성이 대폭 상승했다.

---