LC135: Candy

작성일

https://leetcode.com/problems/longest-consecutive-sequence/

  • 연휴동안 100문제 풀기 (3/100)
  • 완전 어렵게 돌아서 풀어서 이게 맞나 싶다. 코드도 정말 거지같다. 다시풀자.
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct Node {
    int n, dir;
};

class Solution {
public:
    const int DOWN = -1, UP = 1;
    int candy(vector<int>& ratings) {
        queue<Node> q;
        int prev = INT_MAX, dir = DOWN, N = ratings.size();
        vector<int> count(N+2, -1);
        
        count[0] = 0;
        count[N+1] = 0;
        q.push({0,1});
        q.push({N+1,-1});
        
        for(int i = 0; i < N; i++) {
            if(prev < ratings[i] && dir == DOWN) {
                dir = UP;
                count[i] = 1;
                q.push({i, 1});
                q.push({i, -1});
            } else if( prev > ratings[i] && dir == UP) {
                dir = DOWN;
            } else if( prev == ratings[i] && dir == DOWN) {
                count[i] = 1;
                q.push({i,-1});
            } else if( prev == ratings[i] && dir == UP) {
                count[i+1] = 1;
                q.push({i+1,1});
            }
            prev = ratings[i];
        }
        
        while(q.size()) {
            Node cur = q.front(); q.pop();
            int next = cur.n + cur.dir;
            if(!cur.n || cur.n == N+1 || ( next-1 < N && next-1 >= 0 && ratings[next-1] > ratings[cur.n-1])) {
                count[next] = max(count[next], count[cur.n] + 1);
                q.push({next, cur.dir});
            }
        }
        int ans = 0;
        for(int n : count) ans += n;
        return ans;
    }
};