[Programmers] 캐시

LRU 알고리즘을 구현하는 문제이다.

문제풀이 전략
LRU 알고리즘이란 캐시에 존재하는 것 중 가장 오래전에 사용된 것을 제거하고 새로운 것을 캐시에 추가하는 알고리즘이다.

방식은 단순하다.

캐시를 가장 오래전에 사용된 것부터 나열되도록 한 뒤 새 데이터에 접근할 때 캐시에 존재하는지 판단 후 존재한다면 hit 처리를 해 주고, 없다면 캐시의 가장 뒤에 추가해 주면 된다.

hit인 경우 이미 존재하던 것이라도 가장 최근에 사용되었으므로 순서 역시 최신화 하여 맨 뒤로 빼준다.

위의 방식을 코드로 구현하면 쉽게 해결 된다.

팁
map을 사용하여 존재 여부 찾기를 쉽게 수행하였다.
map의 find()를 사용하면 캐시에 이미 존재하는지 아닌지 쉽게 판단할 수 있다.
또한 제거 역시 map의 erase()를 사용하면 쉽게 할 수 있다.
그리고 map은 key를 통한 접근이 되기 때문에 순서 최신화 역시 쉽게 할 수 있다.

코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    map<string, int> m;
    
    for(int i=0;i<cities.size();i++){
        for(int j=0;j<cities[i].size();j++){
            cities[i][j] = toupper(cities[i][j]);
        }
        if(m.find(cities[i]) == m.end()){
            if(cacheSize == 0){
                ;   
            }else if(m.size() < cacheSize){
                m.insert(make_pair(cities[i],i));
            }else{
                auto miter = m.end();
                int midx = i;
                for(auto iter=m.begin();iter!=m.end();iter++){
                    if(midx > iter->second){
                        miter = iter;
                        midx = iter->second;
                    }
                }
                m.erase(miter);
                m.insert(make_pair(cities[i],i));
            }
            answer += 5;
        }else{
            m[cities[i]] = i;
            answer += 1;
        }
    }
    return answer;
}

출처 : https://programmers.co.kr/learn/courses/30/lessons/17680