[C++/Class] Abstract Classes - Polymorphism

문제

---

Abstract Classes - Polymorphism | HackerRank

Abstract Classes - Polymorphism | HackerRank

페이지 교체 알고리즘 (Least Recently Used Algorithm, LRU)을 구현하는 문제입니다.

 

풀이

---

처음에 연결 리스트(Linked List)를 사용하여 캐시 저장소를 관리하려고 해서 코드가 복잡해지고, 구현도 힘들었습니다.

문제를 다시 읽고 주어진 코드를 살펴보다가 Cache 클래스의 Map 타입 객체인 mp 을 전혀 이용하지 않았음을 깨닫고, 연결 리스트는 사용된 값의 순서를 저장하기 위함을 알아챘습니다.

정리하자면, mp 를 이용하여 캐시 저장소를 관리하고, 연결 리스트는 사용한 key 들의 순서를 저장하는 용도입니다.

mp 를 매번 정렬하는 것은 비효율적이므로 연결 리스트를 통해 mp 의 노드를 삭제하거나 삽입, 갱신을 편하게 수행합니다.

 

그림을 통해 어떻게 동작하는지 살펴보겠습니다.

위 그림과 같이 초기화되어 있고, 캐시 저장소의 용량은 5 라고 가정합니다.

이미 존재하고 있는 key 인 '1'을 사용했을 때의 동작입니다.

연결 리스트에서 4번째에 위치해있지만, 사용했으므로 가장 최근에 사용한 key 가 됩니다.

따라서 연결 리스트에서 key '1'의 노드가 맨 앞으로 옮겨지고, Map 에서는 아무런 동작을 하지 않습니다.

가득 차 있는 캐시 저장소에 새로운 key 를 추가하는 경우의 동작입니다.

먼저 연결 리스트의 맨 앞에 새로운 key 의 노드를 추가합니다.

캐시 저장소의 용량은 5 이므로, 가장 나중에 사용된 노드인 Tail 노드를 삭제해줘야 합니다.

우선 새로운 key 가 삽입되기 전의 Tail 노드를 Map 에서 지워주고,
연결 리스트에서도 key '4' 를 삭제한 후 key_ '2' 을 Tail 로 설정합니다.

그리고 새로운 key 인 '6' 을 Map 에 삽입합니다.

 

      void set(int k, int val) {
            Node* new_node = new Node(k, val);

        if (head == NULL) {        // If linked list is empty
                head = new_node;
                tail = new_node;
            }
            else {
                head->prev = new_node;    // Update linked list
                new_node->next = head;
                head = new_node;
            }

            ...

캐시 저장소에 저장된 key 들의 순서를 저장하기 위한 연결 리스트를 만드는 부분입니다.

Node 객체를 동적으로 생성하여 연결 리스트가 비어있을 때 head 와 tail 로 설정해주고,
이미 노드가 존재하면 맨 앞에 추가합니다.

 

      void set(int k, int val) {
              ...

            if (mp.count(k) > 0) {    // If already have that key             
                mp[k]->value = val;    // Update value
                MoveToHead(mp[k]);

                return;       
            }

            if (mp.size() >= cp) {      // If map is fulled
                mp.erase(tail->key);    // Delete tail node

                Node* tmp = tail;    // Delete same node in linked list
                tail = tail->prev;
                delete(tmp);
                tail->next = NULL;
            }
            mp.insert(make_pair(k, new_node));
      }

key 를 캐시 저장소에 채워넣는 부분입니다.

Map 은 중복을 허용하지 않으므로, 이미 key 가 존재할 경우, 해당하는 key 의 값을 갱신해줍니다.

그리고 연결 리스트에서 해당하는 노드를 맨 앞으로 옮깁니다.

 

전체 코드

---

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

struct Node{
   Node* next;
   Node* prev;
   int value;
   int key;
   Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
   Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
};

class Cache{

   protected: 
   map<int,Node*> mp; //map the key to the node in the linked list
   int cp;  //capacity
   Node* tail; // double linked list tail pointer
   Node* head; // double linked list head pointer
   virtual void set(int, int) = 0; //set function
   virtual int get(int) = 0; //get function

};

//Only Edit Here
//----------------------------------------------------------
class LRUCache : public Cache{
    public:
        LRUCache(int c) { this->cp = c; }
        void set(int k, int val) {
            Node* new_node = new Node(k, val);

            if (head == NULL) {        // If linked list is empty
                head = new_node;
                tail = new_node;
            }
            else {
                head->prev = new_node;    // Update linked list
                new_node->next = head;
                head = new_node;
            }

            if (mp.count(k) > 0) {    // If already have that key             
                mp[k]->value = val;    // Update value
                MoveToHead(mp[k]);

                return;       
            }

            if (mp.size() >= cp) {      // If map is fulled
                mp.erase(tail->key);    // Delete tail node

                Node* tmp = tail;    // Delete same node in linked list
                tail = tail->prev;
                delete(tmp);
                tail->next = NULL;
            }
            mp.insert(make_pair(k, new_node));
        }
        int get(int k) {
            if (mp.count(k) > 0) { 
                MoveToHead(mp[k]);

                return mp[k]->value; 
            }
            else { return -1; }
        }
    private:
        void MoveToHead(Node* node) {    // Update order of node in cache
            head->prev = node;
            if (node->prev) { node->prev->next = node->next; }
            if (node->next) { node->next->prev = node->prev; }
            node->prev = NULL;
            node->next = head;
            head = node;
        }
};
//----------------------------------------------------------

int main() {
   int n, capacity,i;
   cin >> n >> capacity;
   LRUCache l(capacity);
   for(i=0;i<n;i++) {
      string command;
      cin >> command;
      if(command == "get") {
         int key;
         cin >> key;
         cout << l.get(key) << endl;
      } 
      else if(command == "set") {
         int key, value;
         cin >> key >> value;
         l.set(key,value);
      }
   }
   return 0;
}