LeetCode 150 - Candy

https://leetcode.com/problems/candy/

 

n 명의 줄 서있는 아이들.

각각의 아이들에는 rating이 할당 돼 있다. 이런 아이들에게 다음 조건에 따라 사탕을 줄 것이다.

• 각각 아이들은 최소한 하나의 사탕을 받아야만 합니다.
• rating이 높은 아이는 인접한 아이보다 더 많은 사탕을 받습니다.

아이들에게 나눠줘야 하는 사탕의 최소 개수를 구하여라.

어차피 1개씩은 다 받아야 하니까 모든 아이에게 1개씩을 나눠주고 보자.

i 기준에서 i-1과 i+1의 값을 비교해야 한다. 양 옆의 값 중 자신보다 작은 값이 존재한다면 사탕을 양 옆보다 더 줘야 한다.

예시를 보겠다.

[1, 0, 2] 일 때 우선 가운데 1번 idx의 아이는 사탕을 1개만 받아도 된다.

0번 idx는 1번 idx보다 rating이 크므로 2개를 받아야 한다.

2번 idx는 1번 idx보다 rating이 크므로 2개를 받아야 한다.

양쪽 방향에서 중앙으로 접근해 가능 방식으로 푸는 게 좋을 것 같다.

• 왼쪽에서 오른쪽 방향으로 훑으면서 오른쪽 이웃과 비교
• 오른쪽에서 왼쪽 방향으로 훑으면서 왼쪽 이웃과 비교

그런데 이 두 결과를 어떻게 합쳐야 할까?

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        // left to right;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // right to left;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                // 이미 더 많다면 추가할 필요가 없다.
                if (candies[i] > candies[i + 1]) continue;
                candies[i] = candies[i + 1] + 1;
            }
        }

        return Arrays.stream(candies).sum();
    }
}

우선 왼쪽 → 오른쪽 방향으로 진행하면서 사탕을 분배한다.

그 후 오른쪽 → 왼쪽 방향으로 진행하면서 사탕을 조건에 따라 분배해야 하는데 만약 rating이 오른쪽보다 높은데도 이미 주어진 사탕이 오른쪽 사탕보다 많다면 더 이상 추가해 줄 필요가 없다.