LC432: All O`one Data Structure

https://leetcode.com/problems/all-oone-data-structure

  • 거의 답을 보고 풀었다. 아이디어는 그나마 똑같이 생각한것을 위안삼는다.
  • STL List의 구조랑 사용법에 대해서 한참 공부했다.
    • 일단 Circular List이다. Head는 항상 의미가 없다.
    • Kernel의 List와 같은 방식이다.
    • Insert 할 경우, 내가 던진 ieterator Node 앞으로 데이터가 들어간다.
  • Iterator를 얻는 아래 패턴은 기억해두자.
1
auto dest = li.find(x), start = dest--;
  • 특정 bound에만 처리해야 하는 일이 추가되는 경우는 bound보다 자료구조를 늘려버리면 코드가 짧아진다.
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
49
50
51
52
53
54
55
56
57
58
59
60
61
class AllOne {
public:
    /** Initialize your data structure here. */
    struct listData {
        int value;
        unordered_set<string> us;
    };
    list<listData> li;
    unordered_map<string, decltype(li.begin())> hash;
    AllOne() {}
  
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        # 비어있으면 0을 집어넣기
        if(!hash.count(key))
            hash[key] = li.insert(li.begin(), {0, {key}});
        
        # find dest to move
        auto dest = hash[key], start = dest++;
        if(dest == li.end() || dest->value != start->value+1)
            dest = li.insert(dest, {start->value+1, {}});
        hash[key] = dest;
        dest->us.insert(key);
        
        # 비엇다면 지우기
        start->us.erase(key);
        if(start->us.empty())
            li.erase(start);
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        # cannot find in the hash -> skip
        if(!hash.count(key)) return;
        
        # find dest to move
        auto dest = hash[key], start = dest--;
        hash.erase(key);
        if (start->value > 1) {
            if(start == li.begin() || dest->value != start->value-1)
                dest = li.insert(start, {start->value-1, {}});
            dest->us.insert(key);
            hash[key] = dest;
        }
        
        # 비엇다면 지우기
        start->us.erase(key);
        if(start->us.empty())
            li.erase(start);
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return li.size() ? *li.back().us.begin() : "";
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return li.size() ? *li.front().us.begin() : "";
    }
};