andy(java)

level - hard

[문제 내용]
n명의 아이들이 줄을 섰고 각 아이들은 등급(?)을 가지고 있습니다.
각 아이들에게 최소 1개씩은 사탕을 나눠주고,
이웃한 아이들보다 등급이 높은아이에겐 더많은 사탕을 주어야합니다.
그렇게 준 사탕의 모든 개수를 반환하면 된다.

[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.

[해결 방법]
각 아이들의 순서와 등급을 map으로 저장한 후
등급을 오름차순으로 정렬한다.
그 정렬된 순서대로 값을 비교하고
정렬된 등급과 매칭 되는 순서정보로 사탕의 수를 늘려가면 된다.

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

        if(ratings.length == 1) {
            return 1;
        }
        
        // 순서와 등급을 저장
        HashMap<Integer, Integer> indexes = new HashMap<>();
        for(int i=0; i<ratings.length; i++) {
            indexes.put(i, ratings[i]);
        }
        
        // 등급을 오름차순으로 정렬
        ArrayList<Integer> keySet = new ArrayList<>(indexes.keySet());
        Collections.sort(keySet, new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return indexes.get(integer).compareTo(indexes.get(t1));
            }
        });

        for(int key : keySet) {
            int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE, cleft = -1, cright = -1;
            // 오른쪽과 왼쪽의 등급과 사탕수를 가져옴
            if(key == 0) {
                right = indexes.get(key+1);
                cright = candies[key+1];
            } else if(key == ratings.length-1) {
                left = indexes.get(key-1);
                cleft = candies[key-1];
            } else {
                right = indexes.get(key+1);
                cright = candies[key+1];
                left = indexes.get(key-1);
                cleft = candies[key-1];
            }
            
            // 왼쪽과 오른쪽보다 등급이 높고 사탕수가 작다면 하나 더 준다
            if(left < ratings[key] && candies[key] <= cleft) {
                candies[key] = cleft+1;
            }
            if(right < ratings[key] && candies[key] <= cright) {
                candies[key] = cright+1;
            }
        }

        for (int candy : candies) {
            result += candy;
        }

        return result;
    }
}