문제

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

구현 전 예상 풀이

분할정복으로 풀겠다.

구현 코드

• 오답 코드
  단순하게 분할정복으로 푸니까 테스트 케이스에서 실패해서 두 번의 수정을 거쳤다.

class Solution {
    int[] ratings;
    int[] candies;

    public int candy(int[] ratings) {
        this.ratings = ratings;
        candies = new int[ratings.length];

        candyRec(0, ratings.length - 1);

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

    private void candyRec(int il, int ir) {
        if (il == ir) {
            candies[il] = 1;
            return;
        }

        int im = (il + ir) / 2;
        candyRec(il, im);
        candyRec(im + 1, ir);

        int left = im;
        int right = im + 1;

        if (ratings[left] > ratings[right]) {
            candies[left]++;
        } else if (ratings[left] < ratings[right]) {
            candies[right]++;
        }
    }
}

• 통과 코드
  plusCandies() 메서드가 추가되면서, 높은 평가를 받은 아이가 이웃보다 더 많은 사탕을 받는 부분이 수정되었다.

class Solution {
    int[] ratings;
    int[] candies;

    public int candy(int[] ratings) {
        this.ratings = ratings;
        candies = new int[ratings.length];

        candyRec(0, ratings.length - 1);

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

    private void candyRec(int first, int last) {
        if (first == last) {
            candies[first] = 1;
            return;
        }

        int mid = (first + last) / 2;
        candyRec(first, mid);
        candyRec(mid + 1, last);

        int left = mid;
        int right = mid + 1;

        plusCandies(left, first, true);
        plusCandies(right, last, false);
    }

    private void plusCandies(int target, int range, boolean direction) {
        int pre;

        if (direction) {
            if (target < range) {
                return;
            }
            pre = target + 1;
        } else {
            if (target > range) {
                return;
            }
            pre = target - 1;
        }

        if (ratings[target] <= ratings[pre] ||
                candies[target] > candies[pre]) {
            return;
        }

        candies[target] = candies[pre] + 1;
        
        if (direction) {
            plusCandies(target - 1, range, direction);
        } else {
            plusCandies(target + 1, range, direction);
        }
    }
}

다른 사람 풀이

public int candy(int[] ratings) {
        int sum=0;
        int[] a=new int[ratings.length];
        for(int i=0;i<a.length;i++)
        {
            a[i]=1;
        }
        for(int i=0;i<ratings.length-1;i++)
        {
            if(ratings[i+1]>ratings[i])
            {
                a[i+1]=a[i]+1;
            }
        }
        for(int i=ratings.length-1;i>0;i--)
        {
            if(ratings[i-1]>ratings[i])
            {
                if(a[i-1]<(a[i]+1))
                {
                    a[i-1]=a[i]+1;
                }
            }
        }
        for(int i=0;i<a.length;i++)
        {
            sum+=a[i];
        }
        return sum;
    }

135. Candy
다른 사람 풀이 링크