[프로그래머스] 캐시

풀이)

LRU의 개념만 잘 알고 있다면 풀 수 있는 문제이다.

LRU는 os 포스팅에서도 다뤘지만

가장 최근 동안 사용하지 않은 것을 교체하는 방식이다.

중요한 점은, 만약 캐시 내에 있는 것을 사용하게 된다면 그것을 최근 사용 상태로 바꿔줘야 한다는 것이다.

그래서

vector <string> cache; 를 선언해 가장 최근에 사용한 것은 백터 내의 맨 뒤에 위치하도록 해줬다.

miss로 인해 캐시 내에 데이터를 삭제할 때는 가장 최근 동안 사용하지 않은 것 

즉, 벡터 맨 앞에 있는 것을 제거해줬다.

주의점

cache 크기가 0일 경우를 생각해줘야한다. -> 무조건 miss만 일어남.

코드)

#include <string>
#include <vector>

using namespace std;

string change(string s){//소문자로 바꿔주는 함수
    for(int i=0;i<s.length();i++){
        if(97 <=s[i] && s[i] <=123) continue;
        else s[i] += 32;
    }
    return s;
}

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++){
        string next = change(cities[i]);
        bool hit = false;

        for(int j=0;j<cache.size();j++){
            if(next == cache[j]){
                hit = true;
                cache.erase(cache.begin()+j);
                cache.push_back(next);
                answer += 1;
                break;
            }
        }
        if(hit) continue;
        cache.push_back(next);
        if(cache.size() > cacheSize) cache.erase(cache.begin());
        answer += 5;
    }
    return answer;
}