[프로그래머스 - C++] [1차] 캐시

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

코딩테스트 연습 - [1차] 캐시

 

풀이

캐시 교체 알고리즘은 가장 오래 안쓰인 것은 뽑아서 교체하는 방식인 LRU알고리즘이 사용된다.

따라서 cache 벡터 안에 있는 string들 중 가장 오래 안쓰인것부터 순서대로 배열될 수 있도록 구현해주며 문제를 해결하였다.

 

1. 캐시의 크기가 0인경우 : 캐시 hit이 절대 일어날 수 없기 때문에 ans = 5* cities.size()하고 return 한다.
2. 그렇지 않은 경우는 for문을 이용해 cities 벡터를 차례로 확인한다.

for문에서는

1. 대소문자를 무시하기 때문에 모두 소문자로 변환하여 확인한다.
2. 현재의 cities[i]가 캐시에 존재하는지 여부를 확인한다.
3. 존재하는 경우 그를 erase하고 다시 cache 벡터의 맨 뒤에 push back해준다. (캐시 hit 이므로 answer++)
4. 존재하지 않는 경우 cache벡터의 크기와 cacheSize를 비교한다. (캐시 miss 이므로 answer+=5)
5. cache 벡터의 크기가 더 작은 경우 해당 city이름을 caches 벡터에 push_back한다.
6. 그렇지 않은 경우엔 cache벡터의 맨 앞(가장 오래 쓰이지 않은 city이름)을 erase하고 city이름을 caches 벡터에 push_back한다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    //캐시 크기가 0
    if(cacheSize == 0){
        answer = cities.size()*5;
        return answer;
    }
    
    
    vector<string> cache;
    for(int i=0; i<cities.size(); i++){
        string check = cities[i];
        transform(check.begin(), check.end(), check.begin(), ::tolower);    // 소문자 변환
        auto it = find(cache.begin(), cache.end(), check);
        //캐시에 있음
        if(it != cache.end()){
            cache.erase(it);
            cache.push_back(check);
            answer++;
            
        }
        //캐시에 없음
        else{
            //캐시에 빈자리 있음
            if(cache.size() < cacheSize)
                cache.push_back(check);
            
            //캐시에 빈자리 없음
            else{
                cache.erase(cache.begin()+0);
                cache.push_back(check);
            }
            answer+=5;
        }
    }
    
    return answer;
}