[Programmers] 캐시

프로그래머스 - 캐시 문제 입니다.

 

문제

일반적인 캐시와 캐시 교체 정책을 생각하면됩니다. LRU 교체 정책이므로

cache hit이면 항상 앞으로 옮겨주고 miss이면 cache가 가득 찼을 경우

맨 뒤의 요소를 제거 후 가장 앞에 현재 데이터를 넣습니다.

앞, 뒤 삽입, 삭제가 빈번하므로 list 사용

 

#include <string>
#include <vector>
#include <list>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0, i, j;
    list<string> cache;
    list<string>::iterator itr;
    bool find = false;
    
    for(i = 0; i < cities.size(); i++) {
        for(j = 0; j < cities[i].length(); j++) {	// 소문자 초기화
            cities[i][j] = tolower(cities[i][j]);
        }
        
        for(itr = cache.begin(); itr != cache.end(); itr++) {
            if(*itr == cities[i]) {		// 캐시에 있는 데이터와 같음 (캐시히트)
                cache.erase(itr);	// 삭제 후
                cache.push_front(cities[i]);	// 가장 앞으로
                find = true;
                answer += 1;
                break;
            }
        }
        
        if(find == false) {		// 캐시에 데이터가 없음 (캐시미스)
            if(cacheSize != 0) {
                if(cache.size() == cacheSize) cache.pop_back();		// 캐시가 가득 찼을 경우, 가장 오래된 데이터 삭제
                cache.push_front(cities[i]);	// 가장 앞으로
            }
            answer += 5;
        }
        find = false;
    }
    return answer;
}