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

난이도: Level 2

출처: 2018 kakao Blind Recruitment

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

 

이 문제를 풀기 전에 운영체제 (Operating Systems) 과목의 개념 중 LRU (Least recently used; 가장 덜 최근에 사용한 항목을 쫒아내기)를 알고 계시면 좋습니다.

 

모르는 분들을 위한 설명:

CPU가 메모리에 접근하는 데에는 비용이 발생합니다. 이 비용을 절감하기 위해 '캐시'라는 개념이 존재합니다.

캐시는 CPU와 같은 칩 안에 내장되어 있으며, 가격이 비싸므로 크기가 메모리보다는 많이 작은 편입니다.

자주 사용하는 값은 메모리가 아닌 캐시에 불러들여 둔다면, 접근할 때마다 비용을 크게 절감할 수 있습니다.

 

캐시는 크기가 한정되어 있으므로, 새로운 값을 추가하려고 할 때 캐시가 이미 다 찼다면, 내보낼 항목을 선택해야 합니다.

LRU는 그 방법 중 하나인데, '가장 덜 최근에 사용한 값을 내보내는' 방법입니다.

추후에 이 값을 다시 참조할지 여부는 확실치 않지만, 지금까지 가장 덜 사용했으니 내보내도 다시 불러들여 올 가능성이 낮다는 아이디어에서 고안한 방법입니다.

 

이제 주어진 문제를 보겠습니다.

문제 내용을 요약하면, 캐시 크기와 도시 이름의 목록이 주어졌을 때, LRU를 기준으로 cache hit와 cache miss에 따른 코스트를 계산하는 문제입니다.

Cache hit란 찾으려는 값이 cache 내에 저장되어 있을 때를 의미하며, cache miss는 찾으려는 값이 cache 내에 없는 경우를 뜻합니다.

cache는 0 <= cache <= 30의 값을 가지며, cities는 최대 100,000개가 주어집니다.

도시 이름은 대소문자 구분을 하지 않으며, cache hit일 경우 1, cache miss일 경우 5의 실행 시간이 소요됩니다.

 

이 문제의 핵심은 LRU를 이 문제에 맞게 구현하는 방법입니다.

먼저 아래와 같이 문제 해결을 위한 접근 방법을 구상해 보았습니다.

 

 

저는 LRU 관리를 위해 아래와 같은 자료구조를 두었습니다.

• unordered_set<string> cached: 캐시된 값의 목록만을 관리 (사용 순서는 여기서 관리하지 않음)
• vector<string> recentlyUsed: 캐시된 값의 순서를 관리 (앞일수록 lease recently used, 뒤일수록 most recently used)

먼저, 주어진 도시 이름이 캐시가 되어 있는지 판단해야 합니다.

unordered_set은 값 삽입/삭제/조회에 평균 O(1)의 시간이 소요되므로, 이를 판별하기에 적합합니다.

recentlyUsed는 vector로 구현하였는데, 최대 30개의 원소를 포함하므로 전체를 탐색하기에 오랜 시간이 걸리지 않습니다.

 

주어진 도시가 먼저 캐시되어 있는지 확인합니다.

캐시되어 있지 않은 경우, 캐시 크기가 이미 다 차 있다면, recentlyUsed의 맨 앞 값을 지웁니다. cached에서도 제거해 줍니다.

이후 캐시 크기에 상관없이, 새 도시 이름을 push_back 합니다. cached에도 추가해 줍니다.

 

주어진 도시가 캐시되어 있다면, cached는 건드릴 필요가 없습니다.

recentlyUsed에서 주어진 도시 이름을 찾아서 지우고, 맨 뒤에 다시 push_back 해 줍니다.

 

코드 링크: GitHub

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/17680
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

int totalTime = 0;
const int miss = 5;
const int hit = 1;
vector<string> recentlyUsed;
unordered_set<string> cached;

using namespace std;

void toLowercase (vector<string> &cities) {
    for (int i = 0; i < cities.size(); i++) {
        for (int j = 0; j < cities[i].size(); j++) {
            if ('A' <= cities[i][j] && cities[i][j] <= 'Z') {
                cities[i][j] += 32;
            }
        }
    }
}

int solution(int cacheSize, vector<string> cities) {
    
    if (cacheSize == 0) return (5* cities.size());
    
    toLowercase(cities);
    
    // cached: 캐시된 도시 이름 목록만을 관리
    // recentlyUsed: 오래 된 도시 이름일수록 앞에 위치
    
    for (auto &city : cities) {
        
        // 새 도시 이름이 캐시에 없는 경우
        if (cached.find(city) == cached.end()) {
            totalTime += miss;
            // 캐시 사이즈가 다 찬 경우
            if (recentlyUsed.size() == cacheSize) {
                if (cacheSize != 0) {
                    cached.erase(recentlyUsed[0]);
                    recentlyUsed.erase(recentlyUsed.begin());
                }
            }
            cached.insert(city);
            recentlyUsed.push_back(city);
        }
        // 새 도시 이름이 캐시에 있는 경우
        else {
            totalTime += hit;
            // 도시 이름을 recentlyUsed에서 찾고, 제거한 후 다시 push
            int i = 0;
            for (i; i < recentlyUsed.size(); i++) {
                if (recentlyUsed[i] == city) {
                    break;
                }
            }
            recentlyUsed.erase(recentlyUsed.begin() + i);
            recentlyUsed.push_back(city);
        }
    }
    
    return totalTime;
}

LRU 외에 문제 해결을 위해 고려해야 할 점이 몇 가지 있습니다.

 

1. 도시 이름은 대소문자를 구분하지 않는다.

이를 위해 저는 toLowercase 함수를 만들고, 주어진 도시 이름들 중 대문자를 전부 소문자로 미리 바꾸어 주었습니다.

이를 정규식을 사용해서 변경할 수 있는지... 확인해 보고 싶었으나, 이 부분은 나중에 찾아보기로...

 

2. cache 크기는 0일 수도 있다.

캐시 크기가 0이라면, 주어진 모든 도시마다 실행 시간이 5가 됩니다.

따라서 단순히 5 * cities.size() 를 해 주면 답을 구할 수 있습니다.