2018 KAKAO BLIND RECRUITMENT[1차] 캐시 c++

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

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> q;
    bool l = false;
    
    vector<string> cities_tmp;
    
    for(int i=0; i<cities.size(); i++) {
        for(int j=0; j<cities[i].length(); j++) {
            if(cities[i][j] >= 'A' && cities[i][j] <= 'Z')
                cities[i][j] = cities[i][j] - 'A' + 'a';
        }
    }
   
    if(cacheSize == 0) {
        answer = 5 * cities.size();
        l = true;
    }
    
    if(!l) {
        for(int i=0; i<cities.size(); i++) {
            bool check = false;
            if(q.size() < cacheSize) {
                for(int j=0; j<q.size(); j++) {
                    if(q[j] == cities[i]) {
                        answer = answer + 1;
                        q.erase(q.begin() + j);
                        q.insert(q.begin(),cities[i]);
                        check = true;
                    }
                }
                if(!check) {
                    q.insert(q.begin(),cities[i]);
                    answer = answer + 5;
                }
            }
            else if(q.size() == cacheSize) {
                for(int j=0; j<q.size(); j++) {
                    if(q[j] == cities[i]) {
                        answer = answer + 1;
                        q.erase(q.begin() + j);
                        q.insert(q.begin(),cities[i]);
                        check = true;
                    }
                }
                if(!check) {
                    q.pop_back();
                    q.insert(q.begin(),cities[i]);
                    answer = answer + 5;
                }
            }
        }
    }
    return answer;
}

LRU 알고리즘을 사용하라고 조건에 나와있다.

LRU 알고리즘은 다른게 아니고 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다.

 

Input : 123145

Output : 5413

 

4초 : 1은 재참조된 것이므로, 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경한다.

6초 : cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.

 

LRU 알고리즘에 대한 이해가 없더라도 문제를 보았을때 큐를 사용한다는걸 떠올려야합니다.

하지만 큐는 인덱스 참조가 불가하므로 vector를 큐처럼 만들어 사용해주었습니다.

 

**참고

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

 ** 문제 조건의 cache hit은 캐시 메모리에 찾는 데이터가 존재할때이며 cache miss는 캐시 메모리에 찾는 데이터가 존재하지 않을때입니다.