[LeetCode] 135. Candy

문제 URL : https://leetcode.com/problems/candy/description/

Candy - LeetCode

 

문제 접근법 :

 

아이들에게 사탕을나눠주는 문제입니다.

모든아이들은 최소 1개이상은 받아야하고 아이들마다 등급이 있는데

아이들이 기분상하지않게 양쪽 옆보다 등급이 높다면 반드시 사탕을 받은 개수는 옆보다는 크게 받아야한다고 하네요

그럴때 사탕수를 최소한으로 나눠주는 값을 구해야합니다.

 

저같은경우는 정렬을 이용해서 풀었는데

우선 아이들에게 그냥 1개씩 전부 나눠줍니다. 그럼 아이들의 수만큼 사탕이 소비되겠죠

 

 1,0,2 라는게 있을때

아이들 양옆을 확인해야하는데 맨왼쪽과 맨오른쪽 은 양옆이라는게 존재하지 않으니

가상의 아이를 생성해 등급을 무한대로 줍니다.

+00 은 무한대로 생각하세요

그럼 +00, 1, 0 ,2 ,+00

정렬을하면   등급0인에가 첫번째이고 등급이 1인애가 2번째 등급이 2인에가 3번째입니다. 무한대인에는 가상이니 셀필요없습니다.

 

0의 양옆은 자신보다 등급이 높은애가 없으니 사탕을 받지못합니다.

리고 1인애는 양옆을 확인해보니 무한대보다는 낮아야하고 0인에보다는 크게 받아야하니 1개를 받으면되겠죠

그리고 2는 0보다는 크게받아야하고 무한대인에보다는 작게받아야하니 1개를 받으면되니

 

아이들의수 + 1+1 이니 5개가 소비되겠쬬

 

소스코드 : 

 

class Solution {
public:
int candy(vector<int>& ratings) {
    int n = ratings.size();
    int res = n;
    vector<pair<int,int>> v={{1e8,0}};
    ratings.insert(ratings.begin(),1e8);
    ratings.push_back(1e8);

    for(int i =0;i<ratings.size();i++)v.push_back({ratings[i],i});
    sort(v.begin(),v.end());
    vector<int> check(n+4);
    for(int i=0;i<n;i++){
        int val,idx;
        tie(val,idx) = v[i];
        if(ratings[idx]>ratings[idx-1]||ratings[idx]>ratings[idx+1]){
            if(ratings[idx]>ratings[idx-1]&&ratings[idx]>ratings[idx+1])
                check[idx] = max(check[idx-1],check[idx+1])+1;
            else if(ratings[idx]>ratings[idx-1])
                check[idx] = check[idx-1]+1;
            else
                check[idx] = check[idx+1]+1;
            res+=check[idx];     
        }
    }
    return res;
}
};

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은언제나 환영입니다.