[프로그래머스]2018 KAKAO BLIND RECRUITMENT : 캐시 (level 2)(c++)

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

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

 

방법 1: 캐시 벡터에 <경과시간, 문자열> 저장하기

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {

    const int HIT = 1;
    const int MISS = 5;
    
    // 캐시 사이즈가 0 일경우
    if (cacheSize == 0)
    {
        return cities.size() * MISS;
    }

    // <경과시간, 문자열>을 저장할 cache벡터 선언
    vector<pair<int, string>> cache(cacheSize);

    int time = 0;
    for (auto iter_city = cities.begin(); iter_city != cities.end(); ++iter_city)
    {
        // 찾을 문자를 대문자로 변환
        transform(iter_city->begin(), iter_city->end(), iter_city->begin(), ::toupper);

        // 한 텀이 지날 때마다 전체에 경과시간을 1씩 더해줌
        for_each(cache.begin(), cache.end(), [](pair<int, string>& pr) {
            ++pr.first;
            });

        // cache벡터에서 해당 도시 찾기
        auto iter_cache = find_if(cache.begin(), cache.end(), [&iter_city](const pair<int, string>& pr) ->bool {
            return pr.second.compare(*iter_city) == 0;
            });

        // cache벡터에서 도시를 찾았을 때
        if (iter_cache != cache.end())
        {
            (*iter_cache).first = 0;

            time += HIT;
        }
        // cache벡터에 도시가 없을 때
        else
        {
            auto lru_iter = max_element(cache.begin(), cache.end());
            (*lru_iter).first = 0;
            (*lru_iter).second = *iter_city;

            time += MISS;
        }
    }

    return time;
}

 

방법 2: 캐시벡터를 큐 처럼 사용하기

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {

    const int HIT = 1;
    const int MISS = 5;
    
    // 캐시 사이즈가 0 일경우
    if (cacheSize == 0)
    {
        return cities.size() * MISS;
    }

    // 캐시를 저장할 벡터, 시간 경과를 저장할 벡터 선언 (큐 처럼 이용)
    vector<string> q(cacheSize);

    int time = 0;
    for (auto iter_city = cities.begin(); iter_city != cities.end(); ++iter_city)
    {
        // 문자를 대문자로 변환
        transform(iter_city->begin(), iter_city->end(), iter_city->begin(), ::toupper);

        // cache벡터에서 해당 도시 찾기
        auto iter_cache = find_if(q.begin(), q.end(), [&iter_city](const string& s) ->bool {
            return s.compare(*iter_city) == 0;
            });
        
        // cache벡터에서 도시를 찾았을 때
        if (iter_cache != q.end())
        {
            q.erase(iter_cache);
            q.push_back(*iter_city);

            time += HIT;
        }
        // cache벡터에 도시가 없을 때
        else
        {
            if (q.size() >= cacheSize)
            {
                q.erase(q.begin());
            }
            if (q.size() < cacheSize)
            {
                q.push_back(*iter_city);
            }

            time += MISS;
        }
    }

    return time;
}

 

 

방법1과 2 모두 장단점이 있다.

	방법 1 :캐시 벡터에 <경과시간, 문자열> 저장하기	방법 2 :캐시벡터를 큐 처럼 사용하기
장점	빠르다. 해당하는 인덱스 값의 갱신만 일어남.	LRU(Least Recently Used) 매커니즘을 그대로 구현할 수 있다.  벡터를 큐처럼 사용하므로, 가장 앞에 있는 요소가 LRU이고, 가장 뒤에 있는 요소가 가장 최근에 사용된 요소이다.
단점	매회 전체 캐시의 시간값이 더해지는 비용이 있다.	자료의 삭제와 추가가 빈번하게 일어난다. 벡터에서 자료를 이동하는 비용이 많이 든다.

 

나는 방법1이 더 빠르기도 하고, 코드가 깔끔하다고 생각한다.

 

 

 

TIP. functor의 활용 - 람다함수

문자열을 찾을 때 람다 함수를 이용하였는데 

첫번째는 예쁘고 = 가독성이 좋고

두번째는 functor를 요구하는 코드 안에서 한번 쓰고 말것이기 때문이다.

 

 

아래는 일치하는 문자열을 찾는 함수 find_if에서 functor로 쓴 람다함수 이다. 

// "iter_city가 가리키는 문자열과 일치하는 문자열"이 포함된 pair을 찾는 람다함수
[&iter_city](const pair<int, string>& pr) ->bool 
{
    return pr.second.compare(*iter_city) == 0;
}

 

 

위 코드에서 쓴 람다함수의 각 요소는 다음과 같다.

[captures](parameters) -> return type { body }  

• capture : iter_city 레퍼런스 참조
• parameter : vector<vector<pair<int, string>> cache의 요소
• return type : bool 형태
• body : pair형태의 cache요소에서 2번째 값이 iter_city가 가리키는 문자열과 동일하면 true반환

 

 

 

람다 함수 사용법을 많이 참고한 싸이트와 블로그 : 

https://blog.koriel.kr/modern-cpp-lambdayi-teugjinggwa-sayongbeob/

Modern C++ lambda의 특징과 사용법

https://en.cppreference.com/w/cpp/language/lambda

Lambda expressions (since C++11) - cppreference.com