Level 2. [1차] 캐시

Level 2. [1차] 캐시

 

 

이 문제는 삽질을 좀 했다.

 

우선 컴퓨터 구조론 때 분명 구현해봤었는데, 너무 오래돼서 그런지 Hit 시에 앞으로 옮기는 걸 깜빡하고 있었다.

• 따라서, 원소의 우선순위를 조정할 수 없는 우선순위 큐를 쓰면 안 된다.

unordered_set을 사용하기도 해봤지만, GCC에서는 삽입된 순서를 유지하지 않아 실패했다.

 

결국, 우선순위 큐나 해시 맵을 통해 시간 복잡도를 더 줄일 수는 없다는 걸 깨닫고 리스트로 해결했다.

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cctype>

using namespace std;

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

    if (cacheSize == 0)
        return cities.size() * 5;

    for (string& city : cities)
    {
        transform(city.begin(), city.end(), city.begin(), ::tolower);

        auto it = find(lst.begin(), lst.end(), city);

        if (it == lst.end())
        {
            answer += 5;

            if (cacheSize <= lst.size())
                lst.erase(lst.begin());
        }
        else
        {
            answer += 1;

            lst.erase(it);
        }

        lst.emplace_back(city);
    }

    return answer;
}