135. Candy

 문제: leetcode.com/problems/candy/

Candy - LeetCode

 적어도 1명의 아이는 1개의 캔디를 가져야하고 자기 옆에있는 친구보다 낮은 rating을 가졌으면 반드시 적은 캔디를 가져야한다.  반대로 rating이 높으면 많은 캔디를 가져야 한다.

4 cases

 기본적으로 V자일 때 두 선분이 만나는 점에서 상대적 rating을 확인하는 작업이 들어간다.  4가지 정도 cases가 있는데 중요한 점은 V자 일때 아래의 점들에서 상대적 rating을 확인하는 작업을 들어가줘야 한다는 것이다.  두 선분이 겹치는 구간 뿐만 아니라 시작점과 끝점에서 선분의 방향이 아래를 가리킨다면 상대적 rating 확인 작업을 해줘야한다.

 생각하면서 테스트케이스를 생각하기 까다로운 점은 V자의 만나는 점에서 해당 점이 점이 아니라 선인 경우가 있을 수 있다.  즉, [5,4,3,2,1,1,1,2,3,4]와 같이 1이 선으로 구성되는 경우가 그것이다.  이러한 경우를 필터링하려면 greater로 조건문을 잡는게 아니라 greater or equal로 조건을 잡아줘야한다.

class Solution {
public:
    void go(vector<int>& ans, vector<int>& ratings, int index){
        // left 
        if(ans[index] == 0) ans[index] = 1;
        int left = index;
        while(left - 1>= 0 && ratings[left - 1] > ratings[left]){
            if(ans[left - 1] < ans[left] + 1){
                ans[left - 1] = ans[left] + 1;
            } else 
                break;
            left--;
        }
        int right = index;
        while(right + 1 < ratings.size() && ratings[right + 1] > ratings[right]){
            if(ans[right + 1] < ans[right] + 1){
                ans[right + 1] = ans[right] + 1;
            } else {
                break;
            }
            right++;
        }
        return;
    }
    
    int candy(vector<int>& ratings) {
        vector<int> ans(ratings.size(), 0);
        for(int i = 0; i < ratings.size() - 1; i++){
            if(ratings[i] <= ratings[i + 1])
                go(ans, ratings, i);
        }
        go(ans, ratings, ratings.size() - 1);
        
        int ret = 0;
        for(int i = 0; i < ans.size(); i++){
            ret += ans[i];
        }
        return ret;
    }
};