일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 109. Convert Sorted List to Binary Search Tree
- 315. Count of Smaller Numbers After Self
- 43. Multiply Strings
- Substring with Concatenation of All Words
- Python Code
- 컴퓨터의 구조
- shiba
- t1
- 운영체제
- 715. Range Module
- kaggle
- DWG
- 파이썬
- attribute
- concurrency
- Class
- 시바견
- 30. Substring with Concatenation of All Words
- iterator
- LeetCode
- Convert Sorted List to Binary Search Tree
- Python Implementation
- 밴픽
- Generator
- Decorator
- Regular Expression
- 프로그래머스
- Python
- data science
- Protocol
Archives
- Today
- Total
Scribbling
[C++] Abstract Class, Polymorphism 본문
https://www.hackerrank.com/challenges/abstract-classes-polymorphism/problem?isFullScreen=true
#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 LinkedList {
private:
int cnt;
Node* head;
Node* tail;
public:
LinkedList() : cnt(0), head(nullptr), tail(nullptr) {
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
void insertNodeToTail(Node* node) {
Node* prev = tail->prev;
prev->next = node;
node->prev = prev;
node->next = tail;
tail->prev = node;
cnt++;
}
int popHead() {
Node* node = head->next;
Node* next = node->next;
next->prev = head;
head->next = next;
int key = node->key;
delete node;
cnt--;
return key;
}
void removeNode(Node* node) {
Node* prev = node->prev;
Node* next = node->next;
prev->next = next;
next->prev = prev;
delete node;
cnt--;
}
int getCnt() {
return cnt;
}
Node* getHead() {
return head;
}
Node* getTail() {
return tail;
}
~LinkedList() {
if (head != nullptr) delete head;
if (tail != nullptr) delete tail;
}
};
class LRUCache : public Cache {
protected:
int cnt;
LinkedList ll;
public:
LRUCache(int capacity): Cache(), cnt(0) {
this->cp = capacity;
tail = ll.getTail();
head = ll.getHead();
}
void set(int key, int val) {
if (mp.find(key) != mp.end()) {
Node* node = mp[key];
mp.erase(key);
Node* newNode = new Node(key, val);
mp[key] = newNode;
ll.removeNode(node);
ll.insertNodeToTail(newNode);
}
else {
// at max capacity
if (cnt == cp) {
int deletedKey = ll.popHead();
mp.erase(deletedKey);
Node* node = new Node(key, val);
mp[key] = node;
ll.insertNodeToTail(node);
}
else {
Node* node = new Node(key, val);
mp[key] = node;
ll.insertNodeToTail(node);
cnt++;
}
}
}
int get(int key) {
// cache miss
if (mp.find(key) == mp.end()) {
return -1;
}
// cache hit
else {
Node* node = mp[key];
mp.erase(key);
int val = node->value;
Node* newNode = new Node(key, val);
mp[key] = newNode;
ll.removeNode(node);
ll.insertNodeToTail(newNode);
return val;
}
}
};
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;
}
'Computer Science > C++' 카테고리의 다른 글
[C++] Object Oriented Programming (0) | 2024.10.01 |
---|---|
[C++] Strings (0) | 2024.09.30 |
[C++] Virtual Functions (0) | 2024.09.28 |
[C++] Regular Expression Matching (0) | 2024.09.26 |
[C++] Priority Queue with custom data type (0) | 2024.02.22 |