99코딩

LRU(Least Recently Used) 알고리즘

가장 오랫동안 참조되지 않은 페이지를 교체하는 방식

기억 공간에 동일한 데이터가 존재하면 해당 데이터를 삭제한 뒤 top에 넣는다.

동일한 데이터가 존재하지 않을 때 기억 공간이 가득 찼다면 가장 오래된 데이터를 삭제한 뒤 새로운 데이터를 넣고

아니라면 바로 데이터를 넣는다. 

풀이 방법

데이터를 앞/뒤에서 삭제하기 용이한 덱(Deque)을 사용하였다.

1. cacheSize가 0이라면 캐시가 없기 때문에 항상 miss이므로 5*cities.size()를 리턴한다.

2. string형 덱 cache를 선언한다.

3. 대소문자 구분을 하지 않으므로 cities[i]를 소문자로 변환시켜준다.

4. miss를 판단할 bool형 cacheMiss를 true로 선언해주고 캐시 내부를 순회하며 cities[i]와 동일한 데이터가 있다면 캐시에서 해당 데이터를 지우고 answer++, cacheMiss = false를 한 다음 break한다.

5. cities[i]를 캐시에 넣는다.

6-1. cacheMiss가 true면 answer에 5를 더해준다.

6-2. cacheMiss가 true고 cache.size()가 cacheSize보다 크면 가장 오래된 데이터를 삭제하고 answer에 5를 더해준다.

7. 반복문이 끝난 후 answer 리턴 

#include <string>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    if(cacheSize < 1) return 5 * cities.size();
    
    deque<string> cache;
    
    for(int i = 0; i < cities.size(); i++) {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        
        bool cacheMiss = true;
        
        for(int j = 0; j < cache.size(); j++) {
            if(cache[j] == cities[i]) {
                cache.erase(cache.begin() + j);
                answer++;
                cacheMiss = false;
                break;
            }
        }
            
        cache.push_back(cities[i]);
        
        if(cacheMiss) {
            if(cache.size() > cacheSize) 
                cache.pop_front();
            answer += 5;
        }
    }
    
    return answer;
}