[스택/큐] 캐시 - 2018 KAKAO BLIND RECRUITMENT

이 문제는 LRU(Least Recently Used) 알고리즘을 구현하는 문제다.

 

해결 방법

LRU 알고리즘은 가장 오랫동안 사용되지 않은 요소를 제거하는 교체 알고리즘이며, 필자가 구현한 방법은 다음과 같다.

먼저, 큐에 있는 요소들을 pop해가며, cache hit이 발생한 요소를 제외하고 모두 임시 큐로 옮겨놨다가 다시 기존 큐로 옮긴다. cache hit이 발생했다면 cache hit이 발생한 요소는 큐의 맨 뒤에 push한다.

만약 cache hit이 발생하지 않았다면 새로운 요소를 큐에 넣어야 하는데, 그 전에 cacheSize를 따져서 큐가 모두 찼다면 가장 오래된 요소를 제거해두면 된다.

마지막으로 cache hit의 여부에 따라 cache hit이 발생했다면 answer에 1을 더하고, cache hit이 발생하지 않았다면 answer에 5를 더하면 된다.

 

 

소스코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

queue<string> q;

int lru(string s, int cacheSize) {
    if(cacheSize==0) return 5;
    bool hit=false;
    queue<string> tmp_q;
    string fs;
    while(!q.empty()) {
        fs=q.front();
        q.pop();
        if(fs!=s) tmp_q.push(fs);
        else hit=true;
    }
    while(!tmp_q.empty()) {
        fs=tmp_q.front();
        tmp_q.pop();
        q.push(fs);
    }
    if(hit) {
        q.push(s);
        return 1;
    } else {
        if(q.size()==cacheSize) q.pop();
        q.push(s);
        return 5;
    }
}

string to_lower(string s) {
    for(int i=0;i<s.length();i++) if(s[i]>=65&&s[i]<=90) s[i]+=32;
    return s;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    for(int i=0;i<cities.size();i++) cities[i]=to_lower(cities[i]); // 소문자로 통일
    for(int i=0;i<cities.size();i++) answer+=lru(cities[i], cacheSize);
    return answer;
}

 

테스트케이스 20개 모두 정답