leetcode - 135. Candy

주제

array

문제

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

n명의 아이들이 있다. n명의 아이들의 평가 ratings가 주어진다.

아이들은 최소한 1개의 사탕은 받아야하며, ratings(평가)가 양옆의 아이보다 높다면 양옆의 아이보다 사탕을 더 많이 가져가야한다.

입출력 예시

예시 1

입력: ratings = [1,0,2]
출력: 5
설명: 첫 번째, 두 번째, 세 번째 아이에게 각각 사탕 2개, 1개, 2개를 할당할 수 있습니다.

예시 2

입력: ratings = [1,2,2]
출력: 4
설명: 첫 번째, 두 번째, 세 번째 아이에게 각각 사탕 1개, 2개, 1개를 할당할 수 있습니다. 
세 번째 아이는 위의 두 조건을 충족하기 때문에 사탕 1개를 받습니다.

조건

• n == ratings.length
• 1 <= n <= 2 * $10^{4}$
• 0 <= ratings[i] <= 2 * $10^{4}$

문제풀이

1. 아이들이 가져가는 캔디를 1로 초기화한다.
2. 먼저 왼쪽에 있는 아이와 평가를 확인한 후 현재 아이의 평가가 높을 경우 왼쪽 아이의 사탕 갯수만큼 더한다.
3. 오른쪽에 있는 아이와 평가를 확인한 후 현재 아이의 평가가 높을 경우에 현재 아이가 가지고 있는 캔디와 오른쪽에 있는 아이가 가지고 있는 캔디 + 1(내가 가지고 있던 초기 캔디) 중 가장 큰 값을 대입한다.
4. 캔디들을 합산하여 리턴한다.

class Solution {
    public int candy(int[] ratings) {
        int result = 0;
        int[] candies = new int[ratings.length];
        for (int i = 0; i < candies.length; i++) {
            candies[i] = 1;
        }

        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] += candies[i - 1];
            }
        }

        for (int i = ratings.length - 1; i >= 1; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candies[i - 1] = Math.max(candies[i - 1], candies[i] + 1);
            }
        }

        
        for (int i = 0; i < candies.length; i++) {
            result += candies[i];
        }
        return result;
    }
}