[Programmers] 캐시

캐시

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

• 입력 형식
  • 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
  • cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
  • cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
  • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
• 조건
  • 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
  • cache hit일 경우 실행시간은 1이다.
  • cache miss일 경우 실행시간은 5이다.

풀이

map["도시명"] = 인덱스 형식으로 캐시에 있는 도시를 저장했다. map을 선택한 이유는 set, map(O(logN))의 search 시간복잡도가 deque(O(N))보다 빠르다.

1. 도시명을 모두 소문자로 통일한다. tolower() 사용
2. cache가 비어있으면 (miss)
   2.1 cache의 크기가 cacheSize보다 작을 때만 도시를 추가한다.
3. cache가 비어있지 않으면
4. cache에 도시가 존재하면 (hit) find() 사용
   4.1 도시에 해당하는 인덱스를 갱신한다.
5. cache에 도시가 존재하지 않으면 (miss)
   5.1 cache의 크기가 cacheSize와 같으면 해당 도시명을 찾아서 삭제한다. LRU 알고리즘
   5.2 도시를 추가한다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    map<string, int> cache; 
    int answer = 0; // 총 실행시간
    
    for(int i=0; i<cities.size(); i++){
        string city = cities[i];
        for (int i=0; i<city.size(); i++) 
            city[i] = tolower(city[i]);
        
        if(cache.empty()) { // miss
            answer+=5;
            if(cache.size() < cacheSize)
                cache[city]=i; // 추가
            continue;
        }
        
        auto it = cache.find(city);
        if(it != cache.end()){ // hit
            answer++;
            cache[city]=i; // 갱신
            continue;
        }

        // miss
        answer+=5;
        if(cache.size()==cacheSize){ // 제거
            string s; // 제거할 도시
            int idx=100005;
            for(auto c:cache){
                if(c.second < idx){
                    s = c.first;
                    idx = c.second;
                }
            }
            cache.erase(cache.find(s));
        }
        cache[city]=i; // 추가          
    }
    
    return answer;
}

정리

deque를 사용한 풀이가 더 깔끔하다.
deque 풀이