[프로그래머스] 2018 KAKAO BLIND 캐시 (level 2)

[문제보기]

 2018 KAKAO BLIND 캐시

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

 

[풀이과정]

일단 cacheSize가 0일 때를 먼저 예외 처리해준다. 이를 처리 안 해주면 밑의 연산에서 에러가 날 수 있기 때문이다.

그리고 문제에서 대소문자는 구분하지 않는다고 제시되었기 때문에 cities의 데이터를 대문자를 소문자로 변환을 

시켜주었다. 

 

이렇게 전처리 과정을 한 뒤, vector cache 변수를 만들어 resize()로 cacheSize만큼 지정해 줬는데, vector의 resize()는

vector의 크기를 cachesize만큼 할당해주는 함수이다. (이때, 크기만 할당이 되고 원소는 없기 때문에, size() 함수를 

출력하면 '0'이 출력된다. 더 정확한 설명은 구글에 vector를 치면 많은 블로그가 나온다.)

 

그러고 나서 for문을 사용하여 cities의 각 원소를 검사해주는데, cache에 cities[i]가 있는지 검사를 하여 있으면 

cache hit, 없으면 cache miss가 나오는 형태로 구현해주면 된다.

이 부분에서 LRU 알고리즘을 사용하라고 제시되어 있기 때문에 필자는 cache에서 찾은 원소를 지우고 cities[i]를 

push_back 해주고, 못 찾으면 cache.begin()를 없애는 형태로 구현을 하였다. 

 

[소스코드]

//캐시
#include <string>
#include <vector>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if(cacheSize == 0){
        answer = 5 * cities.size();
        return answer;
    }
    
    
    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;
        }
    }
    
    vector<string> cache;
    cache.resize(cacheSize);
    for(int i=0; i<cities.size(); i++){
        bool flag = true;
        for(int k=0; k< cacheSize; k++){
            if(cities[i] == cache[k]){
                cache.erase(cache.begin()+k);
                cache.push_back(cities[i]);
                answer += 1;
                flag = false;
                break;
            }
        }
        
        if(flag){
            cache.erase(cache.begin());
            cache.push_back(cities[i]);
            answer += 5;
        }
    }
    
    return answer;
}

 

[해결 과정 중 실수한 부분]

이 문제는 캐시에 대한 지식과 LRU 알고리즘을 알고 있는 사람이면 금방 푸는 문제일 것이다.

하지만 필자는 캐시에 대한 지식은 있었지만, LRU 알고리즘이 정확히 무엇인지 알지를 못해 이 문제가 이해를 못해

풀지를 못했다. 하지만 LRU 알고리즘을 찾고, 이 문제에 대해 생각을 해보니 쉽게 구현을 할 수 있는 문제였다.

아쉽..ㅠㅠ