[LeetCode] 135. Candy

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

Candy - LeetCode

문제 유형 : 그리디

문제 난이도 : Hard

 

문제

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.

 

n명의 학생이 줄을 서 있습니다. 각 학생은 각자의 레이팅이 주어집니다.

당신은 아이들에게 아래의 조건을 만족해야 합니다.

    1. 각 아이들은 최소 하나의 사탕을 받아야 합니다.

    2. 이웃하는 아이들보다 큰 아이는 더 많은 사탕을 가져야 합니다.

 

두 조건을 만족하는 최소의 사탕개수를 구하시오.

 

풀이

사탕의 개수를 담는 배열을 하나 생성합니다. 기본값을 1로 초기화시킵니다.

배열을 왼쪽에서 오른쪽으로 순회하며 이전의 숫자보다 더 크면 사탕을 받을 개수를 늘립니다.

현재의 아이가 이전의 아이보다 더 큰지만 확인하고, 그 반대는 확인하지 않기 때문에 반대로도 확인합니다.

 

반대로 순회하면서 기존의 사탕의 개수(왼쪽 순회)와 새로운 사탕의 개수(오른쪽 순회) 중 더 큰것을 고릅니다.

더 큰것을 고름으로서 2번 규칙을 만족시킬 수 있습니다.

 

배열의 숫자를 모두 더해주면 됩니다.

 

코드(C++)

class Solution {
public:
    int candy(vector<int>& ratings) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        const int n = ratings.size();
        vector<int> candies(n, 1);

        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i-1]) {
                candies[i] = candies[i-1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i+1]) {
                candies[i] = max(candies[i], candies[i+1] + 1);
            }
        }
        
        int sum = 0;
        for (const int num : candies) {
            sum += num;
        }

        return sum;
    }
};