[LeetCode] 432. All O`one Data Structure

https://leetcode.com/problems/all-oone-data-structure/description/?envType=daily-question&envId=2024-09-29

leetcode - All O'one Data Structure

문제 유형 : 해시, 구현

문제 난이도 : Hard

 

문제

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

• AllOne() Initializes the object of the data structure.
• inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
• dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
• getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
• getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

 

문자열의 개수를 저장하고 최대 및 최소 카운트를 반환하는 자료구조를 디자인하시오.

AllOne클래스

- AllOne(): 생성자

- inc(String Key): key의 개수를 1 증가.

- dec(String Key): key의 개수를 1 감소. 0개가 되면, 제거

- getMaxKey(): 가장 많은 카운트의 키들 중 하나를 반환. 없으면 ""반환.

- getMinKey(): 가장 적은 카운트의 키들 중 하나를 반환. 없으면 ""반환.

 

풀이

이중연결리스트와 해시맵, 집합을 이용하여 해결할 수 있다.

 

노드의 구조는 다음과 같다:

int freq: 출현빈도

Node* prev: 이전 노드 포인터

Node* next: 다음 노드 포인터

unordered_set<string> keys: 해당 빈도를 가진 모든 키들

 

AllOne 클래스의 멤버는 다음과 같이 한다:

unordered_map<string, Node*> map: 문자열이 속한 출현빈도를 담은 노드

Node* head; - 이중연결리스트의 Head

Node* tail; - 이중연결리스트의 tail

 

inc(string key) - 

만약 키가 이미 존재하는데, 다음 노드의 빈도가 현재 빈도 +1이 아닌 경우, 새 노드를 만들어줘야 한다.

만약 키가 이미 존재하고, 다음 노드의 빈도가 현재 빈도 + 1이라면, 해당 노드에 키를 추가한다.

그리고, 기존 개수의 노드에 속한 문자열이 없으면, 제거한다.

 

키가 존재하지 않을 경우, 빈도 1짜리에 현재 key를 등록해야 한다.

첫 노드가 없거나 빈도가 1보다 큰경우, 새 노드를 생성하여 등록한다.

1짜리 빈도의 노드가 있다면, 그 노드에 문자열을 소속시킨다.

 

dec(string key) -

만약 키가 존재하지 않으면, 중단한다.

빈도가 1이면 해시맵에서 제거한다.

현재 빈도-1짜리의 빈도를 가진 노드가 있어야 하는데, 없다면, 새로 노드를 만들어서 사이에 놓는다.

있다면, 그 노드에 키를 추가시킨다.

 

기존 빈도의 노드에 키가 없으면 그 노드를 제거시킨다.

 

getMaxKey() - 만약 head와 tail이 붙어있다면, 빈 이중연결리스트이므로 ""를, 아니면 tail의 이전 노드에 있는 문자열을 하나 반환한다.

getMinKey() - 만약 head와 tail이 붙어있다면, 빈 이중연결리스트이므로 ""를, 아니면 head의 다음 노드에 속한 문자열을 하나 반환한다.

 

코드

C++

struct Node {
    int freq;
    Node* prev;
    Node* next;
    unordered_set<string> keys;

    Node(int c) : freq(c), prev(nullptr), next(nullptr) {}
};

class AllOne {
private:
    Node* head;
    Node* tail;
    unordered_map<string, Node*> map;

    void removeNode(Node* node) {
        Node* prevNode = node->prev;
        Node* nextNode = node->next;

        prevNode->next = nextNode;
        nextNode->prev = prevNode;
        delete node;
    }
public:
    AllOne() {
        head = new Node(0);
        tail = new Node(0);
        head->next = tail;
        tail->prev = head;
    }
    
    ~AllOne() {
        Node* current = head;
        while(current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    
    void inc(string key) {
        if(map.find(key) != map.end()) {
            Node* node = map[key];
            int freq = node->freq;
            node->keys.erase(key);

            Node* nextNode = node->next;
            if(nextNode == tail || nextNode->freq != freq + 1) {
                Node* newNode = new Node(freq + 1);
                newNode->keys.insert(key);
                newNode->prev = node;
                newNode->next = nextNode;
                node->next = newNode;
                nextNode->prev = newNode;
                map[key] = newNode;
            } else {
                nextNode->keys.insert(key);
                map[key] = nextNode;
            }

            if(node->keys.empty()) {
                removeNode(node);
            }
        } else {
            Node* firstNode = head->next;
            if(firstNode == tail || firstNode->freq > 1) {
                Node* newNode = new Node(1);
                newNode->keys.insert(key);
                newNode->prev = head;
                newNode->next = firstNode;
                head->next = newNode;
                firstNode->prev = newNode;
                map[key] = newNode;
            } else {
                firstNode->keys.insert(key);
                map[key] = firstNode;
            }
        }
    }
    
    void dec(string key) {
        if(map.find(key) == map.end()) return;

        Node* node = map[key];
        node->keys.erase(key);
        int freq = node->freq;

        if(freq == 1) {
            map.erase(key);
        } else {
            Node* prevNode = node->prev;
            if (prevNode == head || prevNode->freq != freq - 1) {
                Node* newNode = new Node(freq - 1);
                newNode->keys.insert(key);
                newNode->prev = prevNode;
                newNode->next = node;
                prevNode->next = newNode;
                node->prev = newNode;
                map[key] = newNode;
            } else {
                prevNode->keys.insert(key);
                map[key] = prevNode;
            }
        }

        if(node->keys.empty()) {
            removeNode(node);
        }
    }
    
    string getMaxKey() {
        if(tail->prev == head) return "";
        return *(tail->prev->keys.begin());
    }
    
    string getMinKey() {
        if(head->next == tail) return "";
        return *(head->next->keys.begin());
    }
};