[KAKAO_2018] 캐시 (1차)

카카오 2018 Blind recruitment 문제다.

레벨 2 문제로 프로그래머스 링크로 확인해볼 수 있다.

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

코딩테스트 연습 - [1차] 캐시 | 프로그래머스

이 문제는 LRU 알고리즘 기반으로 주어진 캐시 크기와 문자열 배열이 주어졌을 때 실행시간을 구하는 문제다.

먼저 대소문자 구분이 없으므로 모두 소문자로 바꿔주는 로직이 필요하며,

그 다음에 캐시의 크기에 따른 요소의 추가 및 시간 추가를 해주면 된다.

 

만일 캐시의 크기가 다 차지 않은 경우, cache hit이라면 해당 요소를 맨 앞으로 이동해주고 answer을 +1 해주어야 하며,

cache miss일 경우 꽉 차지 않은 경우와 꽉 찬 경우에 대해 나눠서 구현하면 된다.

#include <string>
#include <vector>
#include <deque>
using namespace std;
 
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    int idx = -1;
    deque<string> cache(cacheSize, "");
    int diff = 'a'-'A';
    for(int i=0; i<cities.size(); i++){
        for(int j=0; j<cities[i].length(); j++){
            if('A' <= cities[i][j] && cities[i][j] <= 'Z') cities[i][j] += diff;
        }
    }
    for(int i=0; i<cities.size(); i++){
        string curstr = cities[i];
        bool found = false;
        for(int j=0; j <= idx; j++){
            if(cache[j].compare(curstr) == 0){ // cache hit
                answer++;
                for(int k=j; k>=1; k--){
                    cache[k] = cache[k-1];
                }
                cache[0] = curstr;
                found = true;
                break;
            }
        }
        if(!found){ // cache miss
            answer+=5;
            if(idx < cacheSize-1){ 
                for(int j=idx+1; j>=1; j--){
                    cache[j] = cache[j-1];
                }
                idx++;
                cache[0] = curstr;
            }
            else if(idx == cacheSize-1){
                for(int j=cacheSize-1; j>=1; j--){
                    cache[j] = cache[j-1];
                }
                cache[0] = curstr;
            }
        }
    }
    return answer;
}