(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[1차]) : 캐시

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

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

deque로 푼 문제였습니다.

 

풀이방법

LRU의 이해를 기반으로 구현해야합니다.

크게 세 가지로 나눌 수 있습니다.

 

1. cacheSize == 0이면

 매번 miss나고 cache에는 어떤 원소도 들어갈 수 없습니다. 따라서 cities.size() * 5를 반환합니다.

 

2. 그 외

 매번 cache(deque) 전체를 살펴봐

 hit라면 해당 원소는 참조되었으므로 answer++, 후 해당 원소를 제일 뒤로 보냅니다.

 miss시 chacheSize미만이라면 cache의 제일 뒤에 push합니다.

 cacheSize가 초과했을 때 가장 참조 안된 원소(맨 앞)를 지워줍니다. 

 

Code

#include <bits/stdc++.h>
using namespace std;
using psi = pair<string,int>;
int solution(int cacheSize, vector<string> cities) {
    if(!cacheSize) return cities.size() * 5;
    int answer = 0;
    deque <string> cache;

    for(auto &c: cities)
        for(int i = 0; i < c.size(); i++)
            if('A' <= c[i] && c[i] <= 'Z') 
                c[i] = c[i]-'A'+'a';

    for(int i = 0; i < cities.size(); i++){
        int hit = 0;
        //hit
        for(auto dq = cache.begin(); dq != cache.end(); dq++){
            if(*dq == cities[i]){
                string s = *dq;
                cache.erase(dq);
                cache.push_back(s);
                hit = 1;
                answer++;
                break;
            }
        }

        //miss
        if(!hit){
            if(cache.size() && cache.size() == cacheSize){
                cache.pop_front();
            }                
            cache.push_back(cities[i]);
            answer+=5;
        }
    }
    return answer;
}