[2018 KAKAO BLIND RECRUITMENT 1차] 캐시

문제풀이

LRU알고리즘을 기반으로한 캐시를 만드는 문제입니다.

LRU 알고리즘은 Least Recently Used란 뜻으로 최근꺼를 사용하겠다. 즉, 가장 오랫동안 사용하지 않은 것을 제거한다는 알고리즘입니다. 

매 업데이트시 매 타임의 시간을 시간으로 등록하여 페이지중 가장 시간이 작은(오래된) 페이지를 교체해주면 됩니다. 

 

소스코드

#include <string>
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;
 
typedef struct Cache{
    int time;
    string data;
    Cache(){}
    Cache(int t,string d){
        time =t;
        data = d;
    }
}Cache;
 
vector<Cache> memory;
int min_time = INT_MAX;
string changeLowerCaseStr(string city){
    for(int i=0;i<city.size();i++){
        if(city[i] <='Z' && city[i] >='A')
            city[i] = city[i] -('A'-'a');
    }
    return city;
}
 
int LRU(string city,int cnt){
    int LRU_index=0;
    city = changeLowerCaseStr(city);
    
    for(int i=0; i<memory.size();i++){
        if(memory[i].data == city){//hit
            memory[i].time = cnt;
            return 1;
        }
    }
    for(int i=0;i<memory.size();i++){
        if(memory[i].time < min_time){//제일 시간 적은애부터
            LRU_index = i;
            min_time = memory[i].time;
        }
    }
    memory[LRU_index].time = cnt;
    min_time = cnt;
    memory[LRU_index].data = city;
    
    return 5;
}
 
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if(cacheSize ==0)
        return cities.size()*5;
    memory.assign(cacheSize,Cache(-1,""));
    for(int i=0;i<cities.size();i++){
        answer += LRU(cities[i],i);
        //cout<<answer<<endl;
    }
    return answer;
}
 
int main() {
    vector<string> ex1= { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
 
    printf("%d", solution(3, ex1));
 
}

 

 

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

프로그래머스