LeetCode: 135번 (Candy) [JAVA]

문제 링크

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

Candy - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 전체 배열을 한 번 돌며 특정 구간(연이어 감소하는 구간의 최소점, 연이어 증가하는 구간의 시작점, 혹은 자신과 좌우 rating이 동일한 지점)을 큐에 저장
2. while문으로 전체 큐를 돌며 해당 구간을 시작으로 재귀호출을 통해 증가하는 지점들에 대해 현재 candy값 +1을 저장
3. 이후 전체 candy들의 누적합을 반환

 문제 속 요구하는 사탕의 분배 방식은, 모든 아이들은 최소 1개의 사탕을 받으면서 자신의 옆 아이들의 rating보다 큰 아이들은 사탕을 그들 보다 더 많이 받아야 한다는 것이다. 조건이 단순하기에 아이들간의 rating 점수의 차이가 중요하기 보다는, 단순하게 한 아이의 rating과 양 옆 아이들의 rating보다 크다 작냐만 생각하면 된다.

 이제 이러한 상태에서 최소값(사탕 1개)을 설정해줄 수 있는 지점들을 찾은 다음, 해당 지점을 시작으로 증가하는 부분으로 재귀호출을 반복하며 이전 지점의 candy값 +1을 저장해주면 된다. 이 때 특정 지점에서 양쪽 구간에서 올라온 candy값들이 서로 다를 수가 있는데, 이럴 때는 candy값이 더 큰 쪽으로 값을 저장한다.

 여기서 그럼 사탕 1개를 받는 지점이 어디인지를 찾아내야 하는데, 이는 바로 연속적으로 증가 혹은 감소하는 구간에서의 최소 지점, 혹은 자신과 좌우 rating이 모두 동일한 지점이다. 문제에서 주어진 조건에서 특정 아이가 주변 아이보다 rating이 높을 때만 사탕을 더 받기 때문에, 주변 아이와 rating이 똑같은 경우에는 자신이 덜 받아도 조건에 부합하다. 그러기 때문에 동일한 rating이 연속적으로 발생하는 구간에서는 그 중 한개의 값이 최소값을 받을 수 있게 된다. 그러기 때문에 전체적으로 증가 혹은 감소하는 구간에서도 이 구간이 꼭 연속적이어야 한다.

 이런 조건을 바탕으로 전체 ratings 배열 속 최소값에 부합한 지점들을 따로 큐에 저장해놓고, 이후 큐 속 지점들을 시작으로 증가하는 방향으로 현재 사탕개수 +1을 저장하는 재귀호출을 통해 전체 아이들에게 사탕을 분배하면 된다. 그리고 이 사탕 배열을 돌며 전체 사탕 개수를 계산한 다음 반환하면 된다.

 

class Solution {
    int[] candies;//각 아이마다 candy 저장 배열
    boolean[] visited;//방문 배열

    public int candy(int[] ratings) {
        candies = new int[ratings.length];
        visited = new boolean[ratings.length];
        Queue<Integer> q = new LinkedList<>();
        int answer = 0;

        if (ratings.length == 1) {//전체 ratings 배열 길이가 1이면 단순 1반환
            return 1;
        }

        //전체 요소를 훑으며 오목한 구간의 가장 작은 지점을 큐에 저장
        if (ratings[0] <= ratings[1]) {
            q.add(0);
        }
        for (int i = 1; i < ratings.length - 1; i++) {
            int prev = ratings[i - 1], now = ratings[i], post = ratings[i + 1];

            if (prev >= now && now <= post) {
                q.add(i);
            }
        }
        if (ratings[ratings.length - 2] >= ratings[ratings.length - 1]) {
            q.add(ratings.length - 1);
        }

        while (!q.isEmpty()) {//해당 지점을 시작으로 dfs
            dfs(q.poll(), 1, ratings);
        }

        for (int i = 0; i < candies.length; i++) {//전체 candy 누적합 계산
            answer += candies[i];
        }

        return answer;
    }

    void dfs(int index, int candy, int[] ratings) {
        if (index < 0 || index >= candies.length) {//구간 외면 return
            return;
        }

        if (visited[index]) {//이미 방문한 곳이면 pass
            if (candies[index] < candy) {//다만 지금 candy값이 기존보다 크다면 최신화
                candies[index] = candy;
            }
            return;
        }

        visited[index] = true;
        candies[index] = candy;

        if (index - 1 >= 0 && (ratings[index - 1] > ratings[index])) {//왼쪽
            dfs(index - 1, candy + 1, ratings);
        }

        if (index + 1 < ratings.length && (ratings[index + 1] > ratings[index])) {//오른쪽
            dfs(index + 1, candy + 1, ratings);
        }
    }
}

결과