"2018 KAKAO BLIND RECRUITMENT" > [1차] 캐시

문제: programmers.co.kr/learn/courses/30/lessons/17680

 

<조건>

• 캐시 크기(cacheSize)와 도시 이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

결국 LRU 알고리즘을 구현하는 문제이다.

 

 

문제 풀이:

1. double linkedList를 이용해 LRU 알고리즘을 구현하였다.
2. 리스트에 도시를 추가할 insert() 함수와 리스트에 해당 도시가 존재하는지 찾는 search() 함수를 생성한다.
3. search()
   1. while문을 통해 list를 처음부터 끝까지 스캔한다.
   2. 리스트에 존재하는 도시라면, 리스트에서 해당 도시를 추출해 맨 뒤에 넣는다 -> insert()
   3. 리스트에 없다면 insert() 함수를 호출해 맨 뒤에 넣는다.
4. insert()
   1. 현재 노드의 개수가 캐시의 개수와 같다면(캐시가 꽉 찼다면) 맨 앞 도시를 지우고 새로운 도시를 삽입한다.
5. 위 과정에서 nodeSize를 적절히 + 또는 - 해주어야 한다.

 

주의!

캐시 크기는 0이 될 수 있으므로, 이 부분을 적절히 처리해 줘야 한다.

 

 

 

소스 코드:

#include <string>
#include <vector>

using namespace std;

class LinkedList{
public:
    class node{
        public:
        string name;
        node* left;
        node* right;
        
        node(string cityName){
            name=cityName;
            left=NULL;
            right=NULL;
        }
        node(){
            left=NULL;
            right=NULL;
        }
    };
    int nodeSize;
    int cacheSize;
    node* head;
    node* tail;
    
    LinkedList(int cacheSz){
        nodeSize=0;
        cacheSize=cacheSz;
        head=new node();
        tail=new node();
    }
    bool search(string cityName){
        
        node * cur = head;
        while(cur->right!=NULL){
            cur=cur->right;
            if(cur->name==cityName){
                cur->left->right=cur->right;
                cur->right->left=cur->left;
                
                nodeSize--;
                insert(cur->name);
                delete cur;
                return true;
            }
        }
        
        insert(cityName);
        return false;
    }
    void deleteFront(){
        node* cur = head->right;
        head->right=cur->right;
        cur->right->left=head;
        delete cur;
    }
    void insert(string name){
        node *newNode = new node(name);
        
        if(nodeSize>=cacheSize){
            if(cacheSize==0) return;
            deleteFront();
            nodeSize--;
        }
        
        nodeSize++;
        if(head->right==NULL){
            head->right=newNode;
            newNode->left=head;
            newNode->right=tail;
            tail->left=newNode;
            
            return;
        }
        tail->left->right=newNode;
        newNode->right=tail;
        newNode->left = tail->left;
        tail->left=newNode;
    }
};

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    LinkedList list(cacheSize);
    for(string city: cities){
        for(int i=0;i<city.size();i++){
            if(city[i]<'a'){
                city[i]=city[i]-'A'+'a';
            }
        }
        if(list.search(city)) answer+=1;
        else answer+=5;
    }
    
    return answer;
}