[1차] 캐시(2018 카카오 블라인드 채용)

문제 링크

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

 

 

풀이

뭔가 큐를 쓸까하다가도 우선순위가 LRU가 있으니 vector 컨테이너 한 개로 erase하며 쓸까하다가 또, vector 컨테이너 두 개 쓸까하다가 예전에 공부했던 deque으로 한 번 써보자 해서 써보았다.

내 기억 속에는 deque은 앞과 뒤에서 빼는 것이 좋다고 하여서 이 문제에 적합할 듯 싶었다.

일단은, 선 처리가 있다.

 

1) 캐시사이즈가 0인 것에 대해서 fault가 뜨므로 바로 return 5 * cities.size(); 해주었고

2) 대소문자 구별이 없기 때문에 transform으로 모두 대문자로 바꿔주었다.

 

그리고, cities에 대한 반복문을 돌면서 deque을 이용하여 캐시를 구현하였다.

deque의 size() 만큼 돌면서 first에 있는 것이 최근에 쓰인 LRU이고 back에 있는 것이 교체될 대상이다.(이건 자기가 설정하기 나름인듯...)

그리하여 캐시에 있는 지 검사할 때는 순서가

 

1) 앞에꺼 빼고 해당되는 것과 같지 않으면 push_back();

2) 앞에꺼 빼고 해당되는 것과 같으면 일단 string 지역 변수로 저장하고 hit=true;

3) hit가 true일 때, 앞에다가 넣어줌.(first에 있는 것이 나중에 교체될 대상)

 

그리고, answer를 증가시켜주는 것은

 

1) hit가 아닐 때, answer+=5;

2) hit일 때, answer++;

 

해주었다.

 

그리고 return;

#include <string>
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
#include <cctype>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    deque<string> dq;
    if(cacheSize == 0) return 5*cities.size();
    for(auto& s : cities) transform(s.begin(), s.end(), s.begin(), ::toupper);
    
    for(auto elem : cities)
    {
        bool hit = false;
        int size = dq.size();
        string hitString;
        for(int i=0; i<size; i++)
        {
            string s = dq.front();
            dq.pop_front();
            if(s != elem) dq.push_back(s);
            else
            {
                hitString = s;
                hit = true;
            }
        }
        if(!hit)
        {
            answer+=5;
            if(dq.size() == cacheSize) dq.pop_back();
            dq.push_front(elem);
        }
        else
        {
            answer++;
            dq.push_front(hitString);
        }
    }
    
    return answer;
}