[프로그래머스] 캐시

문제

 

풀이

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

// 대소문자 구분을 하지 않는다
// transform(str.begin(), str.end(), str.begin(), ::tolower);
// 캐시 교체 알고리즘은 LRU(Least Recently Used)

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    
    if(cacheSize == 0) return cities.size()*5;

    for(int i=0; i<cities.size(); i++){
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        auto it = find(cache.begin(), cache.end(),cities[i]);
        //cache miss
        if(it == cache.end()){ 
            answer+=5;
            if(cache.size()==cacheSize){
                cache.erase(cache.begin());
            }
            cache.push_back(cities[i]);
        }
        //cache hit
        //LRU
        else {
            answer+=1;
            cache.erase(it);
            cache.push_back(cities[i]);
        }
    }
    
    return answer;
}

 

LRU (Least Recently Used)

이미지출처 : LeetCode

• LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다.
• 가장 오랫동안 이용되지 않은 페이지는 앞으로도 사용될 확률이 적다는 가설에 의해 만들어졌다.

 

 

---

 

다른 사람 풀이

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

using namespace std;
int solution(int cacheSize, vector<string> cities) {

    vector <string> q;
    int duration = 0;

    for(vector <string>::iterator it = cities.begin(); it != cities.end(); it++){
        transform(it->begin(), it->end(), it->begin(), ::tolower);

        bool flag = false;
        for(vector<string>::iterator itt = q.begin(); itt != q.end(); itt++){
            if(*itt == *it) {
                flag = true;
                duration +=1;
                q.erase(itt);
                q.push_back(*it);
                break;
            }
        }
        if(!flag) {
            duration +=5;
            if(cacheSize != 0 && q.size() >= cacheSize)
                q.erase(q.begin());
            if(q.size() < cacheSize)
                q.push_back(*it);
        }
    }

    return duration;
}

 

 

---

https://ko.wikipedia.org/wiki/Least_Recently_Used

Least Recently Used - 위키백과, 우리 모두의 백과사전