[17680] [1차] 캐시 ⭐⭐

https://school.programmers.co.kr/learn/courses/30/lessons/17680
난이도 ⭐⭐

문제

---

나의 풀이

보자마자 이건 큐다! 생각나서 푼 문제였다. 그런데 실패했다. ㅋㅋㅋ
이유는 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다. 이 조건 때문이었다.

즉 캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고
새로운 녀석을 배치하는 형식으로 동작된다는 것이다. 그래서 꽉 찬 캐시queue에 새 데이터를 넣어줄 땐, 제일 사용되지 않은 데이터를 pop해야 한다는 것이다. 캐시 공간이 2이고 ‘A’, ‘B’가 들어있을 때, ‘A’를 또 넣으려한다면 캐시에 이미 있기 때문에
캐시 공간은 ‘B’, ‘A’가 되는 것이다. 이후 또 다른 데이터 ‘C’ 를 넣을 땐 ‘B’가 pop 되어 사라지고, 저장공간은 ‘A’, ‘C’ 가 되는 것이다.

내 생각대로 구현하려면 find 이나 index 가 필요했기 때문에 queue 로 구현하다가 vector로 변경했다.
그리고 한번 더 실패했는데, 캐시 사이즈가 0 이고 같은 지역 2개가 있을 때 (ex : LA, LA)
캐시 사이즈가 0 이면 push 할 수 없는 테스트 케이스를 놓쳐서 실패했었다. (7, 17번 테스트케이스였음)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<string> cache;

    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 (cache.size() < cacheSize)
        {
            auto it = find(cache.begin(), cache.end(), cities[i]);
            if (it == cache.end())
            {
                if (cacheSize > 0)
                {
                    cache.push_back(cities[i]);
                }
                
                answer += 5;
            }
            else
            {
                if (cache.size() > 0)
                {
                    cache.erase(it);
                }
                
                cache.push_back(cities[i]);
                answer += 1;
            }
        }
        else
        {
            auto it = find(cache.begin(), cache.end(), cities[i]);
            if (it == cache.end())
            {
                if (cache.size() > 0)
                {
                    cache.erase(cache.begin());
                }
                
                if (cacheSize > 0)
                {
                    cache.push_back(cities[i]);
                }
                
                answer += 5;
            }
            else
            {
                cache.erase(it);
                cache.push_back(cities[i]);
                answer += 1;
            }
        }
    }

    return answer;
}