[Algorithm] Programmers :: 캐시

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

프로그래머스

 

int solution(int cacheSize, vector<string> cities) {
 
    list<string> cacheList;
    int answer = 0;
    list<string>::iterator iter;
 
    if (cacheSize == 0)
    {
        return 5 * cities.size();
    }
 
    for (int i = 0; i < cities.size(); i++)
    {
        for (int j = 0; j < cities[i].size(); j++)
        {
            cities[i][j] = tolower(cities[i][j]);
        }
    }
 
    for (int i = 0; i < cities.size(); i++)
    {
        bool isHitted = false;
        iter = cacheList.begin();
 
        while (iter != cacheList.end())
        {
            if (*iter == cities[i]) // Cache Hit
            {
                iter = cacheList.erase(iter); // 어디 위치든 삭제
                cacheList.push_front(cities[i]); // 맨 앞에 넣기 (가장 최근에 사용했으니)
                answer += 1;
                isHitted = true;
            }
            else ++iter;
        }
 
        if (!isHitted) // CacheMiss
        {
            if (cacheList.size() == cacheSize)
            {
                cacheList.pop_back();
            }
            cacheList.push_front(cities[i]);
            answer += 5;
        }
    }
 
    return answer;
}
 

캐쉬구현 문제다. LRU를 사용하라고 언급되어있기 때문에 LRU에 대한 이해도 필요하다.

List를 써서 풀어봤는데, 놀랍게도 List는 처음 써보는 것 같다.

 

일단 LRU의 캐쉬에는 가장 최근에 사용한 순서대로 원소가 들어있어야 한다. 

찾으려는 값이 캐쉬에 있을 경우(Cache Hit), 해당순서의 iter을 erase시키고 맨 앞으로 넣는다(push_front).

여기서 iterator 쓴 사람들은 당연히 아는 내용이겠지만, STL멤버함수인 erase를 수행할 경우, 해당 원소를 삭제하고 다음 iterator을 반환하기 때문에, 반환값을 그대로 iter에 쓰려고 할 경우 iter++은 수행하면 안된다.

 

찾으려는 값이 캐쉬에 없을 경우(Cache Miss), 해당 값을 캐쉬의 맨 앞에 넣는다. 캐쉬가 꽉 차 있을 경우 맨 뒤의 원소를 제거한다. 

이 문제같은 경우 cacheSize가 0인 경우도 있는데, 그걸 좀 나중에 봐버려서 그냥 맨 앞에 따로 if문으로 처리해버렸다..