[프로그래머스][2018 KAKAO BLIND RECRUITMENT][level2][c++] 캐시

문제

2018 KAKAO BLIND RECRUITMENT 1차 캐시

 

문제 링크

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

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

 

기본적으로 LRU(Least Recently Used)에 관한 지식이 있어야 문제를 푸는데 무리가 없을 듯합니다.

LRU는 간단히 말하자면 사용한 지 제일 오래된 데이터부터 교체하는 것을 말합니다.

 

 

위 그림에서 캐시의 크기가 3인 경우 A B C를 넣고 4번째부터는 캐시가 채워져 있으므로 A가 들어올 때는 cache hit이고 시간을 초기화시켜줍니다. D 가 들어왔을 때는 캐시에 D가 존재하지 않기 때문에  cache miss이고 Time이 제일 오래된 A와 교체합니다.

문제에 대한 LRU에 대한 설명은 이 정도로 충분한 것 같습니다.

 

풀이과정

1. 캐시 사이즈가 0일때는 무조건 cache miss 이기때문에 입력값의 길이*5를 답으로 return 하였습니다.

2. 캐시 사이즈가 1이상일때는 문제에서 대소문자를 구분하지 않는다 명시되어있어서 먼저 입력값을 소문자로 변경해줬습니다.

3. 주어진 캐쉬사이즈 크기의 Vector를 만든 후 Vector에 주어진 값과 동일한 값이 있으면 cache hit로 생각하고 그 값을 Vector에서 지운 후 다시 넣어줍니다. (앞에 있을수록 오래되었다고 생각)

4. 만약 Vector에 주어진 값이 없다면 cache miss로 생각하고 맨 앞 데이터를 지우고 뒤에 새로운 입력값을 넣어줍니다.

5. 위 과정을 반복 후  결괏값을 출력합니다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    int frontIndex=0;
    vector<string> cacheArr;
    
    // 0일때는 무조건 miss
    if(cacheSize==0){
        return cities.size()*5;
    }
    
    // 소문자로 변경
    for(int i=0; i<cities.size(); i++){
        for(int j=0; j<cities[i].size();j++){
            if(cities[i][j]<97){
                cities[i][j]+=32;
            }
        }
    }
    cacheArr.resize(cacheSize);
    
    //LRU 형식으로 답 구하기
    for(int i=0; i<cities.size();i++){
        bool check=false;
       for(int j=0; j<cacheSize;j++){
           // 캐쉬 존재
           if(cities[i]==cacheArr[j]){
               check=true;
               cacheArr.push_back(cities[i]);
               cacheArr.erase(cacheArr.begin()+j);
               break;
           }
       }
        if(check){
            answer+=1;
        }
        else{//캐쉬 비존재
            answer+=5;
            cacheArr.erase(cacheArr.begin());
            cacheArr.push_back(cities[i]);
        }
    }
    
    return answer;
}