[프로그래머스 2018 KAKAO BLIND RECRUITMENT] [1차]캐시

programmers.co.kr/learn/courses/30/lessons/17680?language=cpp

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

난이도 : 레벨2

유사한 문제를 가끔 본 듯한 LRU 알고리즘 문제이다.

 

캐시 히트와 캐시 미스를 알아야 문제를 풀 수 있다.

캐시는 메모리에 동일한 값을 찾으면 캐시 히트, 못찾으면 캐시 미스를 낸다.

미스나면 새로운 자리를 찾아야 하기 때문에 비용이 크다.

기억해둘 점은 메모리가 텅 비면 무조건 캐시미스라는 점이다.

 

두 가지 방법으로 구현가능하다.

1. 캐시에 로드된 시점을 저장하여 시점만 업데이트

2. 캐시 미스 발생 시 무조건 마지막에 값을 넣어서 가장 앞에 있는 값이 LRU가 되도록 만들기

 

처음엔 1 나중엔 2로 구현했다.

 

문제에서 대소문자는 구분하지 않는다고 했으므로 문자열 전체를 소문자로 변경했다.

 

#include <algorithm>

string s = "HELLo";
transform(s.begin(), s.end(), s.begin(), ::tolower); //소문자로 변경
transform(s.begin(), s.end(), s.begin(), ::toupper); //대문자로 변경

//리턴값이 존재하지 않는다.

 

유의해야 할점은 캐시 크기가 0일 때이다. 

캐시 크기가 0이면 캐시를 아예 집어넣을 수 없으므로 예외로 빼줘야 한다.

 

처음 풀이

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

using namespace std;


struct s{
    string city;
    int time;
};
vector<s> tmp;
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    int len = cities.size();
    int curSize = 0;

    if(cacheSize == 0){
        return 5*len;
    }
    for(int i=0; i<len; i++){
        string lower = cities[i];
        transform(lower.begin(), lower.end(), lower.begin(), ::tolower);

       if(curSize<cacheSize){
            bool hit = false;
            for(int j=0; j<curSize; j++){
                if(tmp[j].city == lower){
                    //cache hit
                    answer += 1;
                    hit =true;
                    tmp[j].time = i;
                    break;
                }
            }
            if(!hit){
                answer+= 5;
                tmp.push_back({lower, i});
                curSize++;
            }
        }else {
            bool hit = false;
            int leastRecent=i, leastIdx=0;
            for(int j=0; j<curSize; j++){
                if(tmp[j].city == lower){
                    //cache hit
                    answer += 1;
                    hit = true;
                    tmp[j].time = i;
                    break;
                }else if(leastRecent > tmp[j].time){
                    leastRecent = tmp[j].time;
                    leastIdx = j;
                }
            }
            if(!hit){
                answer+= 5;
                tmp[leastIdx] = {lower, i};
            }
        }
    }
    return answer;
}

 

 

두 번째 - iterator 사용

iterator는 포인터와 유사하게 작동한다.

STL 컨테이너에 담긴 요소를 순회할 수 있다.

포인터와 동일하기 때문에 *it은 it이 가리키는 값이다.

vector.erase(iterator)의 경우 iterator에 해당하는 값을 삭제할 수있다. 매우 편함!

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

using namespace std;

vector<string> v;
int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    int curSize = 0;
    
    if(cacheSize == 0){
        return 5*cities.size();
    }
    
    for(vector<string>::iterator it = cities.begin() ; it!=cities.end(); it++){
        transform(it->begin(), it->end(), it->begin(), ::tolower);
        
        bool flag = false;
        for(vector<string>::iterator itt = v.begin(); itt!=v.end(); itt++){
            if(*it == *itt){
                answer += 1;
                flag = true;
                v.erase(itt);
                v.push_back(*it);
                break;
            }
        }
        
        if(!flag){
            answer+=5;
            if(v.size()>=cacheSize){
                v.erase(v.begin());
            }
            v.push_back(*it);
        }
        
       
    }
    return answer;
}