Leetcode Java Candy

문제

Link

코드

class Solution {

  public int candy(int[] ratings) {
    int[] candies = new int[ratings.length];
    Arrays.fill(candies, 1);
    for (int idx = 1; idx < candies.length; idx++) {
      if (ratings[idx - 1] < ratings[idx]) {
        candies[idx] = candies[idx - 1] + 1;
      }
    }
    for (int idx = candies.length - 2; idx >= 0; idx--) {
      if (ratings[idx] > ratings[idx + 1]) {
        candies[idx] = Math.max(candies[idx], candies[idx + 1] + 1);
      }
    }
    int sum = 0;
    for (int candy : candies) {
      sum += candy;
    }
    return sum;
  }

}

결과

Link

설명

1. 주어진 아이들의 점수를 저장한 정수 배열 ratings를 이용하여, 아래의 요구 사항에 맞춰 사탕을 아이들에게 분배하기 위한 최소 개수를 구하는 문제이다.
   • 각 어린이는 최소 한 개 이상의 캔디를 받는다.
   • 주변 아이들보다 점수가 높은 아이는 더 많은 캔디를 받는다.

2. 아이들에게 분배하는 캔디 개수를 저장하기 위한 정수 배열 candies를 ratings의 크기와 동일하게 만들고, 최소 분배 개수인 1을 배열의 모든 자리에 넣어준다.

3. 좌측에서 우측으로 탐색하여 우측에 있는 아이가 점수가 높은 경우, 좌측에 있는 아이가 받는 캔디 개수보다 하나 더 받게 한다.

4. 우측에서 좌측으로 다시 탐색하여 좌측에 있는 아이가 점수가 높은 경우, 좌측에 있는 아이가 받는 캔디의 개수와 우측에 있는 아이가 받는 캔디의 개수에 하나를 더한 값 중 큰 개수를 받게 한다.

5. 아이들이 받는 캔디의 개수를 저장한 candies를 변수 sum에 누계하여 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.