(프로그래머스 c++ KAKAO)캐시

LRU 형태의 캐시이므로 큐 형태로 접근을 하였다.

데이터 접근이 쉽도록 벡터를 사용하였지만, 방식은 큐와 같다.

 

우선 cacheSize가 0이면 캐시가 불가능하므로 데이터 수 * 5를 바로 리턴하였다.

0이 아니라면 for문을 통해 cities.size()만큼 반복한다.

 

대소문자 구분 없이 같은 단어이면 동일하게 처리해야하므로 transform을 사용하여 모두 소문자로 바꿔주었다.

그리고 위에서 선언했던 string형 벡터 cache를 이용한다.

cache에 현재 데이터가 있는지 find() 함수를 통해 찾도록 한다.

만약 itr이 cache.end()라면 cache에는 cities[i]가 없다는 뜻이므로 cache miss가 발생한다.

answer += 5를 해주기 전에 cache.size()를 검사하여 꽉 찼는지 확인한다.

꽉 차있는 경우 맨 앞에 있는 데이터 즉, LRU에서 가장 최근에 썼던 데이터가 아니므로 지워주도록 한다.

 

만약 itr이 cache.end()가 아니라면 cache에 cities[i]가 있다는 뜻이다.

cache hit 이므로 answer++을 해주고, cache에서 그 데이터를 지우도록한다.

왜냐하면 방금 데이터를 접근해서 최근에 사용했다는 것을 나타내기 위해 cache에 맨 뒤에 넣어주어야 하기 때문이다.

 

cache miss나 hit가 나와도 cities[i]의 데이터는 맨 뒤에 넣어주어야 하기 때문에 공통적으로 처리하는 부분이다.

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    
    
    if(cacheSize == 0)
        return 5 * cities.size();
    
    for(int i = 0; i < cities.size(); i++)
    {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        auto itr = find(cache.begin(), cache.end(), cities[i]);
        
        //cache miss
        if(itr == cache.end())
        {
            if(cache.size() == cacheSize)
                cache.erase(cache.begin());
            answer += 5;
        }
        else //cache hit
        {
            answer++;
            cache.erase(itr);
        }
        cache.push_back(cities[i]);
    }
    return answer;
}