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

캐시

문제 링크

캐시

분석

도시 이름 배열을 순서대로 접근하여 처리할 때, 캐시를 사용하여 최소화된 전체 실행 시간을 반환하는 문제입니다.
여기서 캐시(Cache)는 자주 사용하는 데이터를 빠르게 접근하기 위해 저장하는 공간을 의미합니다.

문제 조건을 보면 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용하라고 합니다.
또한 캐시 히트일 경우 실행 시간은 1, 캐시 미스일 경우 실행 시간은 5가 됩니다.

캐시에 현재 접근하려는 도시 이름이 있을 경우 캐시 히트(Cache Hit)라고 하며, 캐시에 없을 경우 캐시 미스(Cache Miss)라고 합니다.

LRU는 최근에 사용된 데이터를 기준으로 캐시를 관리하는 방식이며, 구체적으로 다음과 같습니다.

• 데이터가 사용되면 뒤(가장 최신 위치)로 이동합니다.
• 캐시가 가득 찼을 경우, 가장 오래 사용되지 않은 데이터를 제거합니다.

예시로, 캐시 사이즈가 3일 때 도시 이름을 A, B, C, A, D 순서로 접근해야한다면 다음과 같은 동작 과정을 거칩니다.

1. A에 접근
   • Miss
   • 캐시 A
2. B에 접근
   • Miss
   • 캐시 A, B
3. C에 접근
   • Miss
   • 캐시 A, B, C
4. A에 접근
   • Hit
   • 캐시 B, C, A
5. D에 접근
   • Miss
   • 캐시 C, A, D

이처럼 캐시 미스가 발생했을 때는 캐시가 가득 찬 경우에만 가장 오래된 데이터를 제거하고, 새 도시 이름을 캐싱합니다.
이후 다른 이름들을 순차적으로 접근하여 확인하면서 캐시 미스일 경우 윗 줄의 과정을 반복하다 캐시 히트일 경우 해당 도시 이름을 최신화 해주게 됩니다.

이 과정으로 캐시 히트가 됐을 때 실행 시간을 1 추가하고, 캐시 미스가 됐을 때 실행 시간을 5 추가하여 값을 반환하면 되는 문제입니다.

이 문제에서는 데이터 크기가 크지 않기 때문에 vector나 list를 사용해도 무방합니다.
다만, LRU를 효율적으로 구현하고자 할 경우 list와 unordered_map을 함께 사용하여 탐색과 갱신을 모두 O(1)로 처리하는 방법이 일반적입니다.

풀이

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    // 캐시 크기가 0이면 모든 접근이 Cache Miss
    if (cacheSize == 0)
    {
        return cities.size() * 5;
    }
    
    int answer = 0;
    
    // 캐시의 사용 순서를 관리
    // 앞: 오래된 데이터, 뒤: 최신 데이터
    list<string> cacheList;

    // 빠르게 존재 여부 확인 및 위치 접근을 위해 사용
    // 도시 이름 list iterator
    unordered_map<string, list<string>::iterator> cacheMap;
    
    for (auto city : cities)
    {
        // 대소문자 구분이 없으므로 소문자로 변환
        transform(city.begin(), city.end(), city.begin(), 
                  [](unsigned char c) { return tolower(c); });
        
        // 캐시 히트
        if (cacheMap.find(city) != cacheMap.end())
        {
            answer += 1;

            // 기존 위치 제거
            cacheList.erase(cacheMap[city]);
        }
        // 캐시 미스
        else
        {
            answer += 5;
            
            // 캐시가 가득 찬 경우
            if (cacheList.size() >= cacheSize)
            {
                // 가장 오래된 데이터 제거
                string oldCache = cacheList.front();
                cacheList.pop_front();

                // map에서도 제거
                cacheMap.erase(oldCache);
            }
        }
        
        // Hit와 Miss 모두 동일한 처리
        // 현재 도시를 최신 위치로 삽입
        cacheList.push_back(city);
        
        // map에 iterator 저장
        cacheMap[city] = prev(cacheList.end());
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 도시 이름 목록 순회 $O(n)$
• 도시 이름을 소문자로 변환하는 transform 함수 $O(m)$
  • 상수 취급 가능

공간 복잡도는 $O(c)$입니다.

• 캐시를 의미하는 list<string> $O(c)$
  • c는 cacheSize로 인한 크기
• 캐시를 빠르게 접근하기 위해 사용한 unordered_map $O(c)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.23MB)
테스트 2 〉 통과 (0.02ms, 4.05MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.02ms, 3.62MB)
테스트 5 〉 통과 (0.01ms, 4.19MB)
테스트 6 〉 통과 (0.01ms, 4.11MB)
테스트 7 〉 통과 (0.01ms, 3.59MB)
테스트 8 〉 통과 (0.01ms, 4.54MB)
테스트 9 〉 통과 (0.01ms, 3.66MB)
테스트 10 〉 통과 (0.06ms, 3.63MB)
테스트 11 〉 통과 (21.84ms, 12.4MB)
테스트 12 〉 통과 (0.03ms, 4.2MB)
테스트 13 〉 통과 (0.06ms, 4.14MB)
테스트 14 〉 통과 (0.09ms, 4.2MB)
테스트 15 〉 통과 (0.11ms, 3.62MB)
테스트 16 〉 통과 (0.22ms, 4.18MB)
테스트 17 〉 통과 (0.03ms, 4.22MB)
테스트 18 〉 통과 (0.26ms, 4.2MB)
테스트 19 〉 통과 (0.25ms, 4.2MB)
테스트 20 〉 통과 (0.25ms, 4.06MB)