[c++/프로그래머스] [1차] 캐시

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

프로그래머스

1. LRU 캐시 알고리즘 사용해서 풀면 된다. 

 --> LRU 캐시 알고리즘이란?

         가장 최근에 사용되지 않은 캐시 데이터를 제거하는 방식의 캐시 교체 알고리즘

2. 선입선출을 생각했기 때문에 큐로 풀었지만,,굳이 큐로 풀지 않아도 될 것 같다. (다른 사람들이 푼거 보니 리스트 많이 사용 한듯)

3. 대소문자 구별하지 않는다고 했으니까 다 소문자로 바꿔준다. transform 사용

4. cities[i]가 캐시에 있을 때와 없을 때를 구분해서 풀어준다. 

5. 캐시에 있을 때는 기존에 있던 캐시를 지워주고 맨 마지막에 다시 추가해준다. answer에 1을 더해준다. (cache hit)

6. 캐시에 없을 때는 가장 늦게 들어간 캐시를 지워주고 cities[i]를 추가해준다. answer에 5를 더해준다. (cache miss)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cctype>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    queue<string> q;
    
    for (int i = 0; i < cities.size(); i++) {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
    }

    // 캐시 크기 만큼 도시 이름 넣고, 만약 새로 넣는 도시가 기존에 이미 있으면 + 1 (가장 최신으로 교체해야함)
    // 새로 넣는 도시가 기존에 없으면 가장 오래된 도시 빼고 새로운 도시 넣고 +5
    for (int i = 0; i < cities.size(); i++) {
        bool isCache = false;
        queue<string> tmpQ(q);

        while (!tmpQ.empty()) {
            if (cities[i] == tmpQ.front()) {
                isCache = true;
                break;
            }
            tmpQ.pop();
        }
        //이미 가지고 있을 때 (Cache hit)
        if (isCache == true) {
            answer += 1;
            //기존 큐에서 지우고 새로운 큐 맨 마지막에 넣기
            queue<string> hitQ;
            while (!q.empty()) {
                if (q.front() != cities[i]) {
                    hitQ.push(q.front());
                }
                q.pop();
            }
            q = hitQ;
            q.push(cities[i]);
        }
        //없을 때 (Cache miss)
        else {
            answer += 5;
            if (q.size() >= cacheSize && cacheSize > 0)
                q.pop();
            if (cacheSize > 0)
                q.push(cities[i]);
        }
    }

    return answer;
}