리트코드 - 135. Candy

리트코드 - 135. Candy

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

 

문제 설명

한 줄에 서 있는 n명의 어린이가 있습니다. 각 어린이에게는 정수 배열 ratings에서 주어진 등급 값이 할당되어 있습니다.
다음 요구 사항을 따라 이 어린이들에게 사탕을 나눠주려고 합니다.

• 각 어린이는 최소한 한 개의 사탕을 가져야 합니다.
• 등급이 높은 어린이는 이웃 어린이보다 더 많은 사탕을 받아야 합니다.

어린이들에게 나눠줄 최소한의 사탕 개수를 반환하세요.

 

의사코드

candies = 나눠줄 사탕을 저장할 배열 반복문 시작 (i = 1부터 왼 -> 오른쪽 순회)     if (ratings[i] > ratings[i - 1])        candies[i] = candies[i - 1] + 1 반복문 종료 반복문 시작 (i = ratings.length - 2부터 오른쪽 -> 왼쪽 순회)     if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])         candies[i] = candies[i + 1] + 1 반복문 종료 answer = 0 반복문으로 candies 배열을 모두 더함 answer 리턴

 

풀이코드

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }

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

        return answer;
    }
}

 

코드설명

배열의 요소가 각 어린이의 랭킹으로 랭킹이 높은 아이에게 사탕을 나눠주는 문제다.

문제가 상당히 불친절한데 왜냐하면 같은 랭킹이 주어지면 적게 사탕을 받게되어 뭔가 이상하기 때문이다.

 

예시 1) 배열이 1,3,3,3,1 인 경우 사탕은 1,2,1,2,1 이 된다.

예시 2) 배열이 1,3,2,2,1 인 경우 사탕은 1,3,1,2,1 이 된다.

 

문제에서 주어진 요구사항이 이웃보다만 사탕개수가 많으면 되는 것이기 때문에 현실적으론 이상하지만 논리적으론 이상할 게 없다.

 

본격적으로 배열을 순회하려고 하니 앞 뒤를 모두 따지기가 번거롭다.

이럴 땐 나누어서 생각하면 된다. 분할 정복에서 일부를 해결하고 나머지를 해결하면 되는 것처럼 말이다.

 

1. 먼저 왼쪽에서 오른쪽 순회를 생각해 볼 수 있다. 이렇게 하면 현재 값이 이전 값(왼쪽 값)보다 크다면 사탕을 한 개 더 받을 수 있다.

2. 다음으로 오른쪽에서 왼쪽으로 순회를 한다. 이 때에는 왼쪽 값이 오른쪽 값보다 크면 사탕을 한 개 더 받을 수 있다.

 

단, 2에서는 한 가지 조건이 더 추가된다. 왼쪽 값이 오른쪽 값보다 크면서, 사탕 갯수는 많지 않아야 한다.

이유는 1에서 왼쪽에서 오른쪽으로 순회하면서 왼쪽보다 큰 값에 대해서는 보장받은 상태이다.

2를 통해 오른쪽에서 왼쪽으로 순회하면 다시 오른쪽보다 큰 값에 대해서는 보장받게 되는데...중복이 발생할 수 있다.

 

만약 추가조건이 없다면 1,3,2 라는 배열의 예에서 왼쪽에서 오른쪽 순회시 사탕은 1,2,1 개가 된다.

그리고 오른쪽에서 왼쪽으로 순회시 사탕은 1,3,1 개가 된다.

이것은 문제에서 요구한 조건 아래와 같다.

• 각 어린이는 최소한 한 개의 사탕을 가져야 합니다. -> 만족
• 등급이 높은 어린이는 이웃 어린이보다 더 많은 사탕을 받아야 합니다. -> 만족
• 어린이들에게 나눠줄 최소한의 사탕 개수를 반환하세요 -> 불만족
  

불만족인 이유는 사탕 1,2,1 로도 요구조건이 만족하기 때문이다.

따라서 2에서는 사탕 갯수를 비교해서 크지 않는 조건이 추가되어야 한다.

 

코드로 다시 돌아오면, candies 초기에 Arrays.fill로 모든 배열의 값을 1로 만들어주었다.

따라서 첫번째 반복문은 왼쪽에서 오른쪽 순회를 하는데 i = 1부터 시작해야 한다.

두번째 반복문은 오른쪽에서 왼쪽 순회를 나타내고, 마찬가지로 끝에서 두번째 인덱스인 i = ratings.length - 2부터 시작한다.

 

이후 배열의 값을 모두 더해주면 된다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

초기 실패한 코드

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1]+;
            }
        }

        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }

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

        return answer;
    }
}

반례는 배열 1,3,2,2,1과 같은게 있을 수 있다.

정답 사탕은 1,2,1,2,1 이지만 위 코드대로 하면 1,3,1,2,1 이 되어 오답이 된다.

코드 설명에서 제시한 조건을 처음에 생각하지 못하여 발생한 오답이다.

 

개인적으로 웃겼던 점

리트코드에 문제 아래 discussion이라는 부분이 있는데 가장 추천이 많은 댓글이다.

그렇다..모든 아이들은 같은 사탕을 받아야만 한다....😄

 

정리

배열을 순회할때 조건이 여러개 있을때 나누어서 생각하는 방법