[Programmers] 캐시
LRU 알고리즘을 구현하는 문제이다.
문제풀이 전략
LRU 알고리즘이란 캐시에 존재하는 것 중 가장 오래전에 사용된 것을 제거하고 새로운 것을 캐시에 추가하는 알고리즘이다.
방식은 단순하다.
캐시를 가장 오래전에 사용된 것부터 나열되도록 한 뒤 새 데이터에 접근할 때 캐시에 존재하는지 판단 후 존재한다면 hit 처리를 해 주고, 없다면 캐시의 가장 뒤에 추가해 주면 된다.
hit인 경우 이미 존재하던 것이라도 가장 최근에 사용되었으므로 순서 역시 최신화 하여 맨 뒤로 빼준다.
위의 방식을 코드로 구현하면 쉽게 해결 된다.
팁
map을 사용하여 존재 여부 찾기를 쉽게 수행하였다.
map의 find()를 사용하면 캐시에 이미 존재하는지 아닌지 쉽게 판단할 수 있다.
또한 제거 역시 map의 erase()를 사용하면 쉽게 할 수 있다.
그리고 map은 key를 통한 접근이 되기 때문에 순서 최신화 역시 쉽게 할 수 있다.
코드
#include <string>
#include <vector>
#include <map>
using namespace std;
int solution(int cacheSize, vector<string> cities) {
int answer = 0;
map<string, int> m;
for(int i=0;i<cities.size();i++){
for(int j=0;j<cities[i].size();j++){
cities[i][j] = toupper(cities[i][j]);
}
if(m.find(cities[i]) == m.end()){
if(cacheSize == 0){
;
}else if(m.size() < cacheSize){
m.insert(make_pair(cities[i],i));
}else{
auto miter = m.end();
int midx = i;
for(auto iter=m.begin();iter!=m.end();iter++){
if(midx > iter->second){
miter = iter;
midx = iter->second;
}
}
m.erase(miter);
m.insert(make_pair(cities[i],i));
}
answer += 5;
}else{
m[cities[i]] = i;
answer += 1;
}
}
return answer;
}
출처 : https://programmers.co.kr/learn/courses/30/lessons/17680
Author And Source
이 문제에 관하여([Programmers] 캐시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kms9887/Programmers-캐시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)