문제 푼 날짜 : 2021-08-29

문제

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

접근 및 풀이

문제에서 제시된 캐시 교체 알고리즘 LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법이다.
이를 구현하기 위해서 vector를 이용하였고, 가장 최근에 이용된 것이 맨 마지막에, 가장 오랫동안 참조되지 않은 것을 맨 앞에 위치하도록 하였다.
LRU 알고리즘이 어떤 것인지 안다면 쉽게 풀 수 있는 문제였다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if (cacheSize == 0) {
        return cities.size() * 5;
    }
    vector<string> cache;
    for (string city : cities) {
        transform(city.begin(), city.end(), city.begin(), ::tolower);
        
        auto it = find(cache.begin(), cache.end(), city);
        if (it == cache.end()) { // cache miss
            if (cache.size() < cacheSize) {
                cache.push_back(city);
            } else {
                cache.erase(cache.begin());
                cache.push_back(city);
            }
            answer += 5;
        } else { // cache hit
            cache.erase(it);
            cache.push_back(city);
            answer += 1;
        }
    }
    return answer;
}

결과

피드백

level2 문제를 많이 풀어보고 기본을 다지자.