자바 기초 문제 - 사탕 나눠 주기

문제

 

N 명의 아이들이 한 줄로 서있다.
각각의 아이들은 점수 표를 가지고 있는데 점수 표에 따라 다음과 같은 규칙으로 사탕을 나누어 줘야 한다.

• 적어도 1개 이상의 사탕을 나누어줘야 한다.
• 점수가 높은 아이에게는 바로 옆의 아이 보다는 사탕을 많이 줘야 한다.

N 명의 아이들에 대한 점수 표가 ratings 배열에 주어질 때,
나누어 줘야하는 최소한의 사탕 개수를 출력하세요.

 

입출력 예시

입력	출력
1 2 3	6
3 2 1	6
1 0 2	5
1 2 2	4
1, 3, 5, 3, 1, 3, 5, 7, 5, 3, 1, 0

 

무조건 한개 이상씩 들고있어야하니 기본적으로 하나씩 아이들에게 쥐어 준 후,

이전 아이와 비교해주고 이전 아이의 사탕 개수에 변동이 생기니 이전아이보다 더 이전에 있던 아이와도 다시 비교 후 사탕을 줘야하는지 판단해야한다.

 

import java.util.Arrays;

public class Practice5 {
    public static int solution(int[] ratings) {
		
        // 캔디 개수를 담아둘 배열 생성
        int[] candies = new int[ratings.length];

	// 첫번째 아이부터 마지막 아이까지 진행하는 반복문
        for (int i = 0; i < ratings.length; i++) {
        
            // 캔디는 적어도 한개이상 들고있어야 하니 1개를 부여
            candies[i] = 1;
            
            // 이전 아이와 점수 비교 및 사탕 비교를 진행할 반복문 생성
            // 이전과 현재를 비교했으면 다시 이전과 그 이전을 비교, 이것을 인덱스의 처음까지 가도록 반복
            for (int j = i; j >0 ; j--) {
            	// 이전 아이의 점수가 현재 아이보다 높은데도 캔디수가 적거나 같으면
                if (ratings[j - 1] > ratings[j] && candies[j-1] <= candies[j]) {
                    // 이전아이에게 현재아이의 캔디 수보다 +1 만큼 다시 준다.
                    candies[j-1] = candies[j] + 1;
                    
                  // 현재 아이의 점수가 이전 아이보다 높은데 캔디수가 적거나 같으면 
                } else if (ratings[j - 1] < ratings[j] && candies[j - 1] >= candies[j]) {
                    // 현재아이에게 이전아이의 캔디 수보다 +1 만큼 다시 준다.
                    candies[j] = candies[j-1] + 1;
                }
            }
        }
		
        // 캔디 배열 안에 들어있는 숫자를 전부 더해준다.
        int sum = Arrays.stream(candies).sum();

        return sum;
    }

    public static void main(String[] args) {
        // Test code
        int[] ratings = {1, 2, 3};
        System.out.println("정답 " + solution(ratings));


        ratings = new int[]{3, 2, 1};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 0, 2};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 2, 2};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 3, 5, 3, 1, 3, 5, 7, 5, 3, 1, 0};
        System.out.println(solution(ratings));
    }
}

 

이렇게 푸는 것 말고도 방향성 가지고 반복문 하나만 가지고 푸는 법도 있더라.. 유연하게 사고해야할 것 같다.

개인적으로 문제 풀고 그 풀이를 남기는 용도로 사용하려고 블로그에 게시했습니다.

 

문제 출처 : http://zero-base.co.kr