135. Candy

• 이 문제는 ratings 값이 어떤 식으로 배치 되어 있는가에 따라서 각 아이들이 받을 수 있는 최대 쿠키의 수가 변한다는 점 때문에 풀기가 좀 어려웠다.

• 기본적인 관찰로 얻은 규칙은 아래와 같다.
• 점수가 연속으로 증가 up 할 경우 각 아이들이 받아야 될 쿠키의 수도 1개씩 증가한다.
• 마찬가지로 점수가 연속으로 감소 down 할 경우 각 아이들이 받아야 될 쿠키의 수는 1개씩 감소한다.

• 문제는 점수가 연속으로 증가 up 하다가 이후 연속으로 감소 down 할 경우 변곡점에 위치한 아이가 받아야 될 쿠키의 수는 단순히 연속으로 증가한 숫자 up 로 결정되지 않는다는 점이다.
• 변곡점에 위치한 아이의 쿠키 수는 up > down 이면 up + 1, up < down 이면 down + 1이 된다.

• 위의 관찰을 바탕으로 연속으로 증가 → 연속으로 감소하는 패턴의 쿠키 수를 계산하려면 Solution::calculate 로직과 같이 하면 된다.

• 만일 연속으로 증가 → 연속으로 감소하는 패턴이 반복되면 어떻게 해야 될까?
• 연속으로 증가 → 연속으로 감소하는 패턴이 반복될 경우 패턴과 패턴이 겹치는 지점 (감소 → 증가가 되는 변곡점)의 쿠키 숫자는 겹치게 되므로 해당 숫자 overlap 만큼 빼주어야 한다.
• 만일 패턴과 패턴 사이에 동일한 값이 반복된다면 패턴이 겹치지 않게 되므로 overlap에서는 제외한다.

• 연속으로 증가 → 연속으로 감소 패턴을 찾아내기 위해서 이전에 연속으로 감소하는 패턴이었는지 추적할 필요가 있다 isDown.
• 이를 바탕으로 패턴의 시작점 up & isDown == true 및 이전과 동일한 값이 출현한 경우 prev == curr 에 패턴의 쿠키 숫자를 계산하면 된다.

• 만약 같은 값이 계속해서 반복된다면 위와 같은 패턴이 발생하지 않았다는 의미이므로 최소의 쿠키 값인 1개를 더해주면된다.
• Solution::calculate의 첫번째 라인 부분에 해당한다.

class Solution {
public:
    static inline int calculate(int up, int down) {
        if (up == 0 && down == 0) return 1;
        if (up > down) ++up;
        else ++down;
        return up * (up + 1) / 2 + down * (down + 1) / 2;
    }

    int candy(vector<int>& ratings) {
        int result = 0;
        int overlap = 0;
        bool isDown = false;
        int up = 0;
        int down = 0;
        int prev = ratings[0];
        for (int i = 1; i < ratings.size(); ++i) {
            int curr = ratings[i];
            if (prev < curr) {
                if (isDown) {
                    result += calculate(up, down);
                    up = down = 0;
                    isDown = false;
                    ++overlap;
                }
                ++up;
            } else if (prev > curr) {
                ++down;
                isDown = true;
            } else {
                result += calculate(up, down);
                isDown = false;
                up = down = 0;
            }
            prev = curr;
        }
        result += calculate(up, down);
        return result - overlap;
    }
};