프로그래머스 - [1차] 캐시 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

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

    map<string, int> m;
    vector<pair<int, string>> cacheList;

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

    for (int i = 0; i < cities.size(); i++)
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
    int i;
    for (i = 0; m.size()<cacheSize; i++)
    {
        if (m.find(cities[i]) != m.end())
        {
            answer += 1;
            m[cities[i]] = i;
            for (int j = 0; j <cacheList.size(); j++)
                if (cacheList[j].second == cities[i])
                    cacheList[j].first = i;
        }
        else
        {
            answer += 5;
            m.insert({ cities[i],i });
            cacheList.push_back({ i,cities[i] });
        }

    }

    for (; i < cities.size(); i++)
    {
        // 캐시 히트
        if (m.find(cities[i]) != m.end())
        {
            answer += 1;
            m[cities[i]] = i;
            for (int j = 0; j < cacheSize; j++)
                if (cacheList[j].second == cities[i])
                    cacheList[j].first = i;
        }
        // 캐시 미스
        else
        {
            answer += 5;
            int minId = 0;
            // 가장오래된거 빼고 새로 넣어야함
            for (int j = 1; j < cacheSize; j++)
            {
                if (cacheList[minId].first > cacheList[j].first)
                    minId = j;
            }
            m.erase(cacheList[minId].second);
            cacheList[minId] = make_pair(i, cities[i]);

            m.insert({ cities[i],i });
        }
    }

    return answer;
}

 

먼저 이 문제를 풀려면 LRU(Least Recently Used) 를 알아야 한다. 

간단하게 말하자면 캐시교체 알고리즘 중 하나로, 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다. 

 

이 방식으로 동작하는 캐시가 있을 때, 총 실행시간을 구하는 문제이다. 

캐시의 크기와 도시들의 이름이 벡터로 주어진다. 

 

먼저 도시를 map으로 저장하였다. 

그리고 가장 오래된 페이지를 찾기위해서 순회를 해야되기 때문에 vector를 하나 더 만들었다. 

원소들은 pair<int, string> 으로 언제 참조되었는지와 도시 이름으로 구성되었다. 

 

크게 두개로 for문이 나뉘었는데 첫번째는 캐시가 다 차기전의 동작이고, 두번째는 캐시가 다 찼을 때의 동작이다. 

캐시 히트일때는 map과 vector에서 해당 페이지의 참조시간을 현재로 바꾼다.

캐시 미스일때는 캐시가 다 차지 않았기 때문에 바로 추가한다. 

 

두번째 for문에서는 똑같이 동작하는데 캐시 미스일때 해당 페이지를 삭제후, 새로운 페이지를 캐시에 저장한다.

 

chatgpt한테 물어보니 자료구조를 바꾸면 더 효율적으로 구성이 가능하다.

 

먼저 map은 이진탐색트리로 구성돼있으며 O(logN)의 시간복잡도이다. 

하지만 unordered_map 은 해시맵으로 구성돼있으며 평균적으로 O(1) 이다. 

 

또 vector를 통해 전체를 순회하기 보다 list로 구성해 최근참조한 것을 맨앞으로 옮기는 과정으로 해서 순회를 없앴다. 

또한 지금처럼 삭제, 삽입이 빈번한 경우 list가 더 효과적이다. 이중리스트로 구성돼있어 해당 포인터만 알고있다면 o(1)의 성능이지만 vector의 경우 해당 요소이후 모든 요소를 이동시켜야하기 때문이다. 

 

그리고 unordered_map에서 여기 필요한 포인터를 값으로 가지면된다. 

 

#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    if (cacheSize == 0) {
        return cities.size() * 5;
    }

    list<string> cache;
    unordered_map<string, list<string>::iterator> cache_map;
    int time = 0;

    for (auto& city : cities) {
        transform(city.begin(), city.end(), city.begin(), ::tolower);
        if (cache_map.find(city) != cache_map.end()) {
            // Cache hit
            time += 1;
            cache.erase(cache_map[city]);
            cache.push_front(city);
            cache_map[city] = cache.begin();
        } else {
            // Cache miss
            time += 5;
            if (cache.size() == cacheSize) {
                // Remove the least recently used item
                cache_map.erase(cache.back());
                cache.pop_back();
            }
            // Add the new city to the cache
            cache.push_front(city);
            cache_map[city] = cache.begin();
        }
    }

    return time;
}

자료구조를 무엇을 쓸지 또 언제쓸지 각 자료구조에 대해 학습하고 잘 파악해놔야겠다.