문제
Abstract Classes - Polymorphism | HackerRank
페이지 교체 알고리즘 중 LRU (Least Recently Used) Algorithm 을 구현하는 문제입니다.
풀이
처음에 연결 리스트(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;
}
참고
