[ Top Interview 150 ] 135. Candy

귀찮Lee·2023년 8월 24일

[알고리즘] Top Interview 150

목록 보기

12/40

문제

135. Candy

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.

Input : 각 아이들의 평가 점수 ratings
Output : 규칙을 지켜 아이들에게 사탕을 주었을 때, 사탕의 최소 개수
Condition
- 아이들은 적어도 한 개 이상의 사탕을 받아야 한다.
- 옆에 있는 아이보다 rating이 높은 경우, 그 아이보다 더 많은 사탕을 받아야 한다.

문제 풀어보기

1차 문제 풀이 전략

캔디 1개 받을 사람 선정
- 캔디를 최소한으로 주어야 하기 때문에 양 옆에 있는 사람들보다 rating이 작거나 같으면 1개만 받아도 된다.
캔디 N개 (N > 1) 이상 받을 사람 선정
- 이전 단계에서 선정된 캔디 N-1개를 받은 사람 양 옆에 있는 사람 중, 그 사람보다 rating이라면, 캔디를 N개 받는 대상자가 된다.
- 캔디 N개를 받을 사람이 없다면, 반복을 끝낸다.

1차 작성

class Solution {
    public int candy(int[] ratings) {

        if (ratings.length == 1) {
            return 1;
        }

        int[] candies = new int[ratings.length]; // 각 사람 별 줄 캔디 수
        int countOfCandy = 1; // 대상자가 받을 캔디 개수
        Set<Integer> indexes = new HashSet<>(); // 대상자 위치
		
        // 캔디 1개 받을 사람들 지정
        if (ratings[0] <= ratings[1]) {
            indexes.add(0);
            candies[0] = countOfCandy;
        }
        if (ratings[ratings.length - 1] <= ratings[ratings.length - 2]) {
            indexes.add(ratings.length - 1);
            candies[ratings.length - 1] = countOfCandy;
        }
        for (int i = 1; i <= ratings.length - 2; i++) {
            if (ratings[i] <= ratings[i - 1] && ratings[i] <= ratings[i + 1]) {
                indexes.add(i);
                candies[i] = countOfCandy;
            }
        }

		// 캔디 2개 이상 받을 사람들
        while (indexes.size() != 0) {
            countOfCandy++;
            Set<Integer> newIndexes = new HashSet<>();
            for (int index : indexes) {
                if (index != 0 && ratings[index-1] > ratings[index]) {
                    newIndexes.add(index-1);
                    candies[index-1] = countOfCandy;
                }
                if (index != ratings.length-1 && ratings[index + 1] > ratings[index]) {
                    newIndexes.add(index+1);
                    candies[index+1] = countOfCandy;
                }
            }

            indexes = newIndexes;
        }
        
        // 총 캔디 수 계산
        int totalCandy = 0;
        for (int candy : candies) {
            totalCandy += candy;
        }
        return totalCandy;
    }
}

2차 문제 풀이 전략

양 옆에 있는 사람들의 사탕 받는 개수를 통해 자신이 받을 개수를 정함
- 양 옆에 있는 사람들보다 rating이 적거나 같은 경우
  - 캔디 1개 받음
- 양 옆에 있는 사람들보다 rating이 높은 경우
  - 둘 중 캔디를 많이 받는 사람보다 1개 더 받음
- 둘 중 한 명보다만 rating이 높은 경우
  - rating이 적은 애보다 1개 더 받음
구현 고려 사항
- 각 자리마다 People 객체 생성
- 각 candy 값이 반복적으로 계산되는 것을 막기 위해 캐싱을 사용

2차 작성

class Solution {
    public int candy(int[] ratings) {

        List<People> peoples = Arrays.stream(ratings)
                .mapToObj(People::new)
                .collect(Collectors.toList());

        for (int i = 0; i < peoples.size() - 1; i++) {
            peoples.get(i).setRight(peoples.get(i + 1));
        }
        for (int i = 1; i < peoples.size(); i++) {
            peoples.get(i).setLeft(peoples.get(i - 1));
        }
        
        return peoples.stream().mapToInt(People::getCandy)
                .sum();
    }

    class People {
        private final int rate;
        private People left;
        private People right;
        private Integer candy;

        People(int rate) {
            this.rate = rate;
        }

        public void setLeft(People left) {
            this.left = left;
        }

        public void setRight(People right) {
            this.right = right;
        }

        public int getCandy() {
            if (candy != null) {
                return candy;
            }

            if (isMoreThanLeft() && isMoreThanRight()) {
                candy = Math.max(left.getCandy(), right.getCandy()) + 1;
                return candy;
            }
            if (!isMoreThanLeft() && !isMoreThanRight()) {
                candy = 1;
                return candy;
            }
            if (isMoreThanLeft() && !isMoreThanRight()) {
                candy = left.getCandy() + 1;
                return candy;
            }
            if (!isMoreThanLeft() && isMoreThanRight()) {
                candy = right.getCandy() + 1;
                return candy;
            }

            return candy;
        }

        private boolean isMoreThanLeft() {
            if (left == null) {
                return false;
            }
            return this.rate > left.rate;
        }

        private boolean isMoreThanRight() {
            if (right == null) {
                return false;
            }
            return this.rate > right.rate;
        }
    }
}

각 방법의 장단점

1번 방법의 경우
- 코드를 기본적으로 읽기 힘들다.
- 2번 방법보다는 성능이 더 잘 나온다.
- 왜인지 더 효울적인 방법이 있을 듯한 느낌이다.
2번 방법의 경우
- 조금 더 객체지향적이고 코드가 읽기 쉽다.
- 각 rating마다 People 객체를 생성해야 하기 때문에 상대적으로 비용이 많이 들어간다.

모범 답안

모범 답안 분석

우선, 각 사람들의 받는 candies 설정 (기본값 : 1)
앞에서부터 순회하면서
- 바로 앞에 있는 rating보다 크다면, 이전에 받은 캔디보다 1개 더 많이 받도록 설정
뒤에서부터 순회하면서
- 바로 뒤에 있는 rating보다 크다면, 기존 값과 (이전에 받은 캔디) + 1 중에 큰 값으로 설정한다.

모범 답안 코드

class Solution {
    public int candy(int[] ratings) {

        int[] candies = new int[ratings.length];
        for (int i = 0; i < candies.length; i++) {
            candies[i] = 1;
        }
        for (int i = 0; i < ratings.length - 1; i++) {
            if (ratings[i + 1] > ratings[i]) {
                candies[i + 1] = candies[i] + 1;
            }
        }
        for (int i = ratings.length - 1; i > 0; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candies[i - 1] = Math.max(candies[i] + 1, candies[i - 1]);;
            }
        }

        int sum = 0;
        for (int i = 0; i < candies.length; i++) {
            sum += candies[i];
        }
        return sum;
    }
}