[Hackerrank] 20. Abstract Classes - Polymorphism

20. Abstract Classes - Polymorphism

[ 난이도: Hard | 분야: Classes ]

1. 과제

과제 설명

C++에서의 추상 기저 클래스들은 오직 기저 클래스로만 사용된다. 그렇기에, 정의하지 않고도 가상 멤버를 허용한다.

캐시는 미래에 데이터를 요구할 때 데이터를 좀 더 빠르게 제공하기 위해  저장하는 공간이다.

캐시에 저장된 데이터는 더 빠른 연산을 가능하게 하거나 같은 데이터가 다른 곳에 저장되어 있다.

cache hit는 필요한 데이터가 캐시에 있을 때를 의미하고 cache miss는 그렇지 않을 때를 의미한다.

cache hit는 캐시에서 데이터를 읽은 뒤 제공하기 때문에 결과를 다시 연산하거나 느린 저장장치에서 읽어오는 것보다 빠르다.

그렇기에, 요청하는 데이터가 캐시에 많이 있을수록 시스템 성능은 비약적으로 증가한다.

유명한 캐시 교체 정책 중 하나는 least recently used(LRU)이다.

이 방식은 사용한지 가장 오래된 아이템을 먼저 버린다.

예를 들어, 만약 5개의 키를 저장할 수 있는 캐시가 아래의 과정을 따른다면(가장 최근의 것이 제일 왼쪽에 있다.)

5 3 2 1 4

만약, 다음 키가 1이라면(cache hit이다), 캐시의 상태는 다음과 같다

1 5 3 2 4

만약 다음 키가 6이라면(cache miss이다), 캐시의 상태는 다음과 같다

6 1 5 3 2

여기서 4가 버려진 이유는 용량이 5인 캐시에서 사용한지 가장 오래 되었기 때문이다. 이 이후에는 다시 4가 나오기 이전까지는 캐시에 없는 상태이다.

주어진 추상 기저 클래스 Cache의 멤버 변수와 함수:

mp - 키를 연결 리스트의 노드와 맴핑

cp - 용량

tail - 더블 연결 리스트의 꼬리 포인터

head - 더블 연결 리스트의 헤드 포인터

set() - 키 값을 설정하거나 입력한다. 만약 존재한다면, 키를 제일 최근에 사용한 것으로 저장한다.

만약, 캐시 용량이 꽉 차면, 가장 오랫동안 사용 안한 키를 새로운 키로 바꾼다.

get() - 만약 키 값이 캐시에 존재한다면, 항상 양수인 키 값을 얻고 그렇지 않다면 -1을 반환한다.

Cache 클래스에서 확장된 LRUCache를 작성해라. 그리고 멤버 함수와 변수들을 사용하여 LRU cache를 구현하라.

 

입력 형식

첫 번째 줄은 get 또는 set 명령을 포함한 줄이 N개 있음을 알려주고 캐시 용량이 M임을 알려준다.

따라오는 N개의 줄은 get 또는 set 명령어를 포함한다.

get으로 시작하는 명령줄은 키만을 포함한다.

set으로 시작하는 명령줄은 키와 캐시 안에 삽입하거나 바꿀 값을 포함한다.

 

제약 사항

N은 1 보다 크거나 같고 500,000보다 작거나 같다.

M은 1 보다 크거나 같고 1000보다 작거나 같다.

key는 1보다 크거나 같고 20보다 작거나 같다.

value는 1보다 크거나 같고 2,000보다 작거나 같다.

 

출력 형식

에디터에서 제공하는 코드는 get 명령어가 들어왔을 때 내가 정의한 LRUCache 클래스에서 출력을 하도록 설계되어 있다.

 

입력 예시

3 1
set 1 2
get 1
get 2

 

출력 예시

2
-1

 

설명

캐시 용량은 1이고, 첫 번째 줄을 통해 key 1을 2로 설정한다. 첫 번째 get은 key 1이 캐시에 있기 때문에 cache hit이고 그것의 값인 2를 출력한다. 두 번째 get은 key 2가 cache에 없기 때문에 cache miss이고 -1을 출력한다.

 

문제

#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

};

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;
}

정답

#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

};

class LRUCache: Cache {
    public:
        LRUCache(int cap) {
            cp = cap;
            tail = NULL;
            head = NULL;
        }
        void set(int myKey, int myValue) {
            if(head == NULL && tail == NULL) {
                // Initialize
                Node *myNode = new Node(myKey, myValue);
                //Node myNode = Node(myKey, myValue);
                //mp.insert({myKey, &myNode});
                mp.insert({myKey, myNode});
                head = myNode;
                tail = myNode;
            }
            else if (mp.find(myKey) == mp.end()) {
                // No value - Cache Miss
                // Node myNode = Node(nullptr,head,myKey,myValue);
                Node *myNode = new Node(NULL, head, myKey, myValue);
                // mp.insert({myKey, &myNode});
                Node* tempAddr;
                if(mp.size() == cp) {
                    // full cache
                    mp.erase(tail->key);
                    tail->prev->next = NULL;
                    tempAddr = tail;
                    tail = tail->prev;
                    delete tempAddr;
                }
                mp.insert({myKey, myNode});
                head->prev = myNode;
                head = myNode;
                
                // If cache doesn't full, no action to do.
            }
            else {
                // Cache hit
                Node* myAddr = mp[myKey]; // Node Addr of current key
                myAddr->value = myValue; // Set the value
                if(myAddr == head) {
                    // myKey locates at head
                }
                else if(myAddr == tail) {
                    // myKey locates at tail
                    tail->prev->next = NULL;
                    tail = myAddr->prev;
                    myAddr->prev = NULL;
                    head->prev = myAddr;
                    myAddr->next = head;
                    head = myAddr;
                }
                else {
                    // myKey locates at middle
                    myAddr->prev->next = myAddr->next;
                    myAddr->next->prev = myAddr->prev;
                    myAddr->prev = NULL;
                    head->prev = myAddr;
                    myAddr->next = head;
                    head = myAddr;
                }
            }
        }
        int get(int findKeyVal) {
            if(mp.find(findKeyVal) == mp.end()) {
                return -1;
            }
            else {
                Node* findAddr = mp[findKeyVal];
                if(head==findAddr && tail==findAddr) {
                    return findAddr->value;
                }
                if(findAddr == tail) {
                    findAddr->prev->next = NULL;
                    tail = findAddr->prev;
                    findAddr->prev = NULL;
                    head->prev = findAddr;
                    findAddr->next = head;
                    head = findAddr;
                }
                else if(findAddr == head) {
                    // No Action to do.
                }
                else {
                    findAddr->prev->next = findAddr->next;
                    findAddr->next->prev = findAddr->prev;
                    findAddr->next = head;
                    head->prev = findAddr;
                    findAddr->prev = NULL;
                    head = findAddr;
                }
                return findAddr->value;
            }
        }
};

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;
}

 

 

 

 

 

ⓒ Hackerrank. All Rights Reserved.