[프로그래머스] 캐시

도시이름 배열과 cache크기가 주어졌을 때, 비용 계산을 하는 문제.

캐시 교체 알고리즘은 LRU인데 이는 Queue와 Map을 같이 적절히 이용하면 구현할 수 있다. Map의 Key 개수를 캐시에 담긴 데이터의 수로 보고 만약 Key의 개수가 cacheSize보다 커진다면 Queue의 맨 앞부터 불러와 Map을 갱신시킨다.

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

cpp code

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    for (string& s : cities) {
        for (char& ch : s) {
            if (ch >= 'a' && ch <= 'z') ch -= 'a' - 'A';
        }
    }
    
    if (cacheSize == 0) return cities.size() * 5;
    
    queue<string> Q;
    map<string, int> M;
    
    for (int i=0; i<cities.size(); i++) {
        if (M.find(cities[i]) == M.end()) answer += 5;
        else answer += 1;
        
        Q.push(cities[i]);
        M[cities[i]]++;
        
        while (M.size() > cacheSize) {
            if (--M[Q.front()] == 0) {
                M.erase(Q.front());
            }
            Q.pop();
        }
    }
    
    return answer;
}