[Programmers]#Level2_캐시, unordered_map 컨테이너, LRU, transform 알고리즘

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. unordered_map 컨테이너 

 

[Basic C++] #72_unordered_map

 

unordered_map 컨테이너는 C++ 표준라이브러리에서 제공하는 비 순차 연관 컨테이너입니다. um 컨테이너는 키와 값을 쌍으로 해시 자료구조에 저장하며, 중복을 허용하지 않고 정렬 상태를 유지하지 않습니다.

 

2. LRU(Least Recently Used)

 

LRU는 캐싱 전략 중 하나로 가장 최근에 사용되지 않은 데이터를 우선적으로 Swap(캐시 Miss 발생 시 필요한 데이터를 기존의 캐시에 저장된 데이터와 교체하는 작업)합니다. 따라서, LRU는 기본적으로 시간 지역성(Temporal Locality)에 기반합니다. 

 

3. HIT? +1초 & 현재 시간 추가, MISS? +5초 LRU 기반의 SWAP!

 

1. 먼저, transform() 알고리즘을 통해 도시 이름을 모두 소문자로 변환합니다.
2. um 컨테이너(해시 자료구조)에 현재 도시 이름을 키 값으로 find() 알고리즘을 수행하고, 찾았다면 HIT, 못 찾았으면 MISS로 분기합니다.
3. HIT의 경우, 최종 소요 시간에 +1 해주고, 현재 도시에 대한 가장 최근 접근 시간을 현재 시간으로 업데이트해줍니다.
4. MISS의 경우, 최종 소요 시간에 +5 해주고, um 컨테이너를 순회하며 가장 최근에 접근하지 않은 도시를 찾아 삭제해 주고, 현재 도시와 현재 시간을 쌍으로 um컨테이너에 삽입해 줍니다.
5. 최종 소요 시간을 결과 값으로 반환해 줍니다.

 

---

 

#3. 코드

 

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

using namespace std;

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

    // { city_name, last_used }
    unordered_map<string, int> cache;
    
    for(int i=0; i<(int)cities.size(); ++i)
    {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        auto it = cache.find(cities[i]);
        // #1. Hit : +1 실행 시간
        if(it != end(cache))
        {
            answer += 1;
            it->second = i;
        }
        // #2. Miss : +5 실행 시간
        else
        {
            answer += 5;
            // cache가 비어있지 않을 때
            if(!cache.empty()&& (int)cache.size() == cacheSize)
            {
                // #1. LRU 수행
                int minHit = INT_MAX;
                string minHitCity = "";
                for(auto it = begin(cache); it != end(cache); ++it)
                {
                    if(it->second < minHit)
                    {
                        minHitCity = it->first;
                        minHit = it->second;
                    }
                }
                cache.erase(minHitCity);
            }
            cache.insert({cities[i], i});
        }
    }
    return answer;
}

 

---