[프로그래머스 / C++] 캐시

https://school.programmers.co.kr/learn/courses/30/lessons/17680
2018 KAKAO BLIND RECRUITMENT

LRU!! 반가웠다. cache hit 과 cache miss 를 언급하는 것 보니 운영체제와 결합된 문제라 딱 면접용 문제로 좋은 것 같다.

대소문자 무시한다 했으니까 일단 전부 소문자로 바꾸고

LRU니까..
만약에 해당 도시가 캐시에 있는 경우 > vector에서 뽑아서 맨 뒤에 넣음
만약에 해당 도시가 캐시에 없는 경우 > vector의 맨 앞에 것을 뽑고 맨 뒤에 해당 도시를 추가.

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

//게시물을 가져오는 부분이 오래 걸린다 -> 캐시 크기를 얼마로 해야 최대 효율일까
// LRU
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    if(cacheSize == 0){
        answer += cities.size() * 5;
        return answer;
    }
    
    vector<string> cache;
    for(int i = 0; i < cities.size(); i++){
        string std = cities[i];
        for(int j = 0; j < std.size(); j++){
            std[j] = tolower(std[j]);
        }
        
        auto it = find(cache.begin(), cache.end(), std);
        if(it != cache.end()){
            cache.erase(it);
            cache.push_back(std);
            answer++;
        }
        else{
            if(cache.size() < cacheSize) cache.push_back(std);
            
            
            else{
                cache.erase(cache.begin() + 0);
                cache.push_back(std);
            }
            answer += 5;
        }
        
    }
    
    return answer;
}

처음엔 벡터 두 개를 선언해서
인덱스 별로 타이머를 부여해줘서 안 바뀌면 ++ ,바뀌면 초기화, 같다면 앞에 거 이런 식으로
하려했는데 이러면 너무 오버헤드가 클 것 같았다. (실제로 운체에서도 이래서 크다구 했다)
반대로 가장 최근에 사용한 걸 가장 나중에 써야 되니까 그냥 뒤에 붙이면 해결 될 거라고 생각했다.