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

문제

 

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

프로그래머스

문제풀이

 

문제에서 캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다고 한다.

용량이 부족한 경우 가장 오랫동안 사용되지 않은 캐시를 교체한다.

 

map 두 개를 이용한다. 하나는 key는 인덱스, value는 도시이름이고 오름차순으로 정렬한다.

다른 하나는 key는 도시이름, value는 인덱스로 구성된 map이다.

도시를 입력받으면 {도시, 인덱스}, {인덱스, 도시}로 두어 도시를 알면 인덱스를, 인덱스를 알면 도시를 알 수 있도록 했다.

 

문제의 입력을 보면 "NewYork"과 "newyork"이 들어올 수 있다, 대소문자 구분을 하지 않으므로 미리 touuper을 통해 모든 문자를 대문자로 바꿔준다.

 

그다음은 캐시 히트를 했는지 판별해야 한다. find를 통해 도시가 map에 있는지, 있으면 답에 1을 더하고, 두 map을 갱신한다. key가 인덱스인 map은 인덱스를 바꿔야 하므로 지웠다가 새로 추가한다.

 

그 외의 경우는 모두 캐시 미스이다. 답에 5를 더하고 두 맵에 새로 추가한다.

만약 맵의 크기가 캐시크기를 넘겼다면 오랫동안 사용되지 않은 캐시를 교체한다. (가장 낮은 인덱스)

 

 

코드

#include <string>
#include <vector>
#include <map>
#include <cctype>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer(0), idx(0), idx2(0);
    map<string, int>db;
    map<int, string>priority;
    for (idx = 0; idx < cities.size(); ++idx) {
        for (idx2 = 0; idx2 < cities[idx].size(); ++idx2) {
            cities[idx][idx2] = toupper(cities[idx][idx2]);
        }
        if (db.find(cities[idx]) != db.end()) {
            answer += 1;
            priority.erase(db[cities[idx]]);
            db[cities[idx]] = idx;
            priority[idx] = cities[idx];
        }
        else {
            answer += 5;
            db[cities[idx]] = idx;
            priority[idx] = cities[idx];
            if (cacheSize < db.size()) {
                auto iter = priority.begin();
                db.erase(iter->second);
                priority.erase(iter);
            }
        }
    }

    return answer;
}