[프로그래머스 lv2] [1차] 캐시 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

LRU(Least Recently Used) 는 정해진 캐시 사이즈가 다 찼을 때 가장 최근에 사용되지 않은 녀석(가장 옛날에 사용된 녀석)을 캐시에서 제거하고 새로운 녀석을 넣는 방법이다.

 

아래의 코드에서는 map을 이용하여 cache를 구현했는데, map의 key는 도시 이름, value는 가장 최근에 참조된 시간을 기록한다.

cache에 이미 도시에 대한 정보가 들어있다면(cache hit), 총 실행시간에 1을 더하고 해당 도시의 최근 참조 시간을 변경한다.

cache에 도시에 대한 정보가 없다면(cache miss) 총 실행시간에 5를 더한다.

이 때, cache가 꽉차있다면 가장 옛날에 참조된 도시(최근 참조 시간이 가장 작은 것)를 map에서 제거하고, 여유 자리가 확보되었을 때 현재 도시의 이름과 참조 시간을 추가하면 된다.

 

모든 도시를 참조한 후 총 실행시간을 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

string tolowerstr(string s) {

    string ret = "";
    for (auto x : s) 
        ret += tolower(x);
    return ret;
}

int solution(int cacheSize, vector<string> cities) {

    map<string, int> m;

    int t = 1, sum = 0;
    for (auto x : cities) {       
        x = tolowerstr(x);
        if (m.find(x) != m.end()) { //cache hit
            sum += 1;
            m[x] = t;
        }
        else { //cache miss
            sum += 5;
            if (cacheSize && m.size() >= cacheSize) {
                int mn = t+1;
                auto mit = m.begin();
                for (auto it=m.begin(); it!=m.end(); it++) {
                    if (mn <= it->Y) continue;
                    mn = it->Y;
                    mit = it;
                }
                m.erase(mit);
            }
            if (cacheSize) m[x] = t;
        }
        t++;
    }
    return sum;
}