[프로그래머스] [1차] 캐시 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/17680#qna

프로그래머스

 

풀이 방법

LRU.. 작년 운영체제 수업 듣기전에 LRU가 뭔가싶어 따로 공부하고 풀어봐야지 했던 문제

우연찬게 이번학기에 운영체제 수강하고 딱 보니 뭔 소리인지 이해가 갔다.!

 

LRU는 운영체제 시간에 배우고 간단한 기법이므로

구글링을 통해 학습해도 충분할듯하다!

 

vector를 사용하여 LRU를 구현했다.

앞쪽에 있을수록 오래된 페이지이고, 뒤쪽에 있을수록 최근에 사용된 페이지로 가정하고 사용했다.

 

기존에 캐시에 있던 페이지가 참조가 된 경우에

vector에서 삭제하고 다시 맨 뒤에 push_back을 해준다.

 

기존에 없던 페이지이고, 캐시 공간이 있다면

push_back을 바로해주면 된다.

 

상세한 로직은 코드에 주석을 달아놨으니 보자!!!

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    // cache 뒤쪽에 있을수록 최근에 사용한것임.
    vector<string> cache;
    for(int i=0; i<cities.size(); i++) {
        
        // 도시를 소문자로 변환
        for(int j=0; j<cities[i].length(); j++) {
            cities[i][j] = tolower(cities[i][j]);
        }
        
        
        // 캐시에서 도시 검색
        int idx=-1;
        for(int j=0; j<cache.size(); j++) {
            if(cities[i] == cache[j]) {
                idx=j;
            }
        }
        
        if(idx==-1) { // 캐시에 존재하지 않음
            answer+=5;
        
            // empty() 체크 안하면 cache 크기 0과 cacheSize 0이 일치해버려서 없는 빈 cache에서 erase가 일어나 fault!
            if(!cache.empty() && cache.size()==cacheSize){ // 캐시 자리가 없다면
                cache.erase(cache.begin());
            }
            if(cacheSize>0) { // 캐시 크기가 0 초과라면 캐시를 쓸 수 있다.
                cache.push_back(cities[i]);
            }
            
        } else { // 캐시에 존재함
            answer+=1;
            cache.erase(cache.begin()+idx); // 캐시에서 삭제후
            cache.push_back(cities[i]); // 맨 뒤로 보내주기 (vector 뒤로 갈수록 최근에 사용한 것임.)
        }   
    }
    
    return answer;
}