[리트코드] 135. Candy

문제

https://leetcode.com/problems/candy/?envType=study-plan-v2&envId=top-interview-150

 

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

---

✔ 문제접근 #1 그리디(정렬)[통과] ⭕

Intuition
우선순위를 기준으로 낮은 값부터 인덱스를 오름차순한다.

오름차순한 인덱스를 기준으로 사탕값을 주변값과 비교하여 갱신해 나간다.

Algorithm
priority 리스트를 통해 {우선순위값, 인덱스}값을 놓고 우선순위 오름차순으로 정렬한다.

정렬된 인덱스값을 기준으로 사탕값을 주변과 비교하여 갱신해나간다.

class Solution {
    
    private List<int[]> priority = new ArrayList<>();
    private int[] candy;
    
    private void compareLeft(int r, int i, int[] ratings) {
        if (r > ratings[i + 1] && candy[i] <= candy[i + 1]) {
            candy[i] = candy[i + 1] + 1;
        }       
    }
    
    private void compareRight(int r, int i, int[] ratings) {
        if (r > ratings[i - 1] && candy[i] <= candy[i - 1]) {
            candy[i] = candy[i - 1] + 1;
        }
    }       
    
    public int candy(int[] ratings) {
        // 방법 : 그리디 -> 낮은 우선부터 사탕 쌓기
            
        // 사탕관리하기
        int n = ratings.length;
        candy = new int[n];
        for(int i = 0; i < n; i++) {
            candy[i] = 1;
        }
        
        // 우선순위 뽑아내기
        for (int i = 0; i < ratings.length; i++) {
            priority.add(new int[]{ratings[i], i});
        }
        Collections.sort(priority, (a, b) -> Integer.compare(a[0], b[0]));

        
        // 사탕이 1개밖에없으면 그냥 끝내기
        if (n == 1) {
            return 1;
        }
            
        
        // 우선순위에 따라 사탕지급
        for (int[] pair : priority) {
            int r = pair[0];
            int i = pair[1];
            
            if (i == 0) {
                compareLeft(r, i, ratings);
            } else if(i == n - 1) {
                compareRight(r, i, ratings);
            } else {
                compareLeft(r, i, ratings);
                compareRight(r, i, ratings);
            }
        }
            
                    
        return Arrays.stream(candy).sum();
    }
}

 

Complexity Analysis

• 시간 복잡도 : O(NlogN)
  • 사탕배열 생성 O(N)
  • 우선순위 리스트 정렬 O(NlogN)
  • 우선순위에 따라 사탕개수 갱신 : O(N)
  • 전체시간복잡도 : O(NlogN)

• 공간복잡도 : O(N)
  
  • ratings의 크기만큼 우선순위 리스트, 사탕 배열 사용

---

기타풀이 및 회고

배열의 최대크기가 2*10**4였기 때문에 완전탐색은 처음부터 안될것이라고 생각하였다. 사탕의 최소를 구하는것이기 때문에 "가장 작은 우선순위 들끼리 먼저 사탕 개수를 갱신해나가면 될 것 같다!" 라고 생각보다 바로 떠올랐다. 그리디에 Hard문제였지만 생각보다는 어렵지 않았던 것 같다.

 

간만에 파이썬이 아닌 자바로 풀이해보았는데, 여전히 구현속도는 파이썬보다 조금 느린 것 같다..ㅋㅋㅋ 혹시 모르니 항상 대비해두자!