프로그래머스 - [1차]캐시

 LRU가 무엇인지 알아야 풀 수 있는 문제다.

컴퓨터구조, 운영체제, 데이터베이스 등 필수 과목에서 한번씩 나오는 개념인데 가장 사용한 지 오래된 것을 캐시에서 빼내겠다는 뜻이다. 캐시는 매우 유용하지만 너무 커지면 오히려 느려지고 무엇보다 비용이 많이든다.

 

예를들어, 

 

캐시의 크기가 3이고 캐시에 A B C 순서로 들어왔다고 하자, 그리고 D가 들어왔다.

-> 가장 사용한지 오래된(들어온지 오래된) A가 빠지고 B C D 형태가 될 것이다.

 

그런데 D가 아니라 A가 들어왔다면, 캐시 히트로 캐시에는 변화없다. 그 다음 D가 들어왔다면?

-> A는 들어온지 가장 오래되었지만 방금 캐시 히트로 썼기 때문에 사용한지 가장 오래됐고 사용한적 없는 B가 빠진다. 그러므로 A C D 형태가 된다.

 

이 알고리즘을 작성하는 것이 이 문제의 핵심이다. 난 list 자료구조를 사용했다. set, map은 자동 정렬이 되어버려서 들어온 순서를 잊어버리게 되고 vector 는 pop, push _back 만 가능하기 때문이다. list는 pop_front back 모두 가능하다. 

 

위 두번째 예를 다시 살펴보자

 

A B C 에서 A가 들어왔다. 그럼 A는 이제 가장 늦게 pop되어야한다. 그러므로

B C A 형태로 바꿔주고 다음 D가 들어오면 pop_front, push_back(D) 하면 C A D 형태가 될 것이다. (위는 A C D 인데 사실 캐시의 순서는 상관이없다.)

 

즉, 우선적으로 빠져야할 원소가 가장 front에 있어야한다는 것이 핵심이다. (back에 있도록 하고 싶다면 그래도된다.)

 

1. 캐시의 자리가 남아있다면 그대로 들어옴 answer + 5

2. 캐시 히트이면 히트된 원소를 가장 back으로 빼줌 answer + 1

3. 캐시 미스인데 자리가 없다면 가장 front에서 빼고 push_back answer + 5

 

LRU를 실제로 구현해보는 건 처음인데 재밌는 문제다. 그리고 이렇게 CS에서 응용해 나올 수 도 있구나 느꼈다.

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <list>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    list<string> LRU;
    if(cacheSize == 0)
        return cities.size() * 5;
    
    for(auto citi : cities){
        transform(citi.begin(), citi.end(), citi.begin(), ::tolower);

        if(LRU.empty()){ // 캐시 비어있음
            LRU.push_back(citi);
            answer += 5; // 캐시 미스
        }
        else if(find(LRU.begin(), LRU.end(), citi) == LRU.end()) { // 못찾음
            if(LRU.size() < cacheSize){
                LRU.push_back(citi);
                answer += 5;
            }
            else{ // LRU
                LRU.pop_front();
                LRU.push_back(citi);
                answer += 5;
            }
        }
        else{
            LRU.remove(citi);
            LRU.push_back(citi);
            answer += 1;
        }
    }
   
    return answer;
}