LC135: Candy

작성일

https://leetcode.com/problems/candy/

  • 일단 Array 문제인지 모르고 걍 set으로 $O(N\log{N})$으로 풀었다. 그 와중에 풀이가 지저분하다. -_-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int candy(vector<int>& ratings) {
        set<pair<int,int>> s;
        for(int i = 0; i < ratings.size(); i++)
            s.insert({ratings[i],i+1});
        vector<int> candy(ratings.size()+2);
        vector<int> rat(1);
        rat.insert(rat.end(), ratings.begin(), ratings.end());
        rat.push_back(0);
        int ans = 0;
        for(auto& [r, p]:s) {
            if(r > rat[p-1] && r > rat[p+1])
                candy[p] = max(candy[p-1], candy[p+1])+1;
            else if(r > rat[p-1] && r <= rat[p+1])
                candy[p] = candy[p-1]+1;
            else if(r <= rat[p-1] && r > rat[p+1])
                candy[p] = candy[p+1]+1;
            else
                candy[p] = 1;
            ans += candy[p];
        }
        return ans;
    }
};
  • 근데 이게 TwoPoint로 풀린단다. 심지어 $O(N), O(1)$으로 풀린단다.
  • 일단 Two-Array 풀이를 고민해 보자면.. (복습하자)
    • 왼쪽 기준으로 candy 쌓고, 오른쪽 기준으로 candy 쌓아서 걍 max하면 될것 같다.
    • 오른쪽 진행과 왼쪽 진행 서로 영향을 안주기 때문이다.
  • 그리고 상수 공간 진행은.. 증감을 번갈아가면서 확인하고, 개수를 샌 뒤에 $N(N+1)/2$를더해주는 것이다. (역시나 복습)