2018 카카오 블라인드 코테 1차 캐시

문제

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

프로그래머스

정답 코드

#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    //list를 사용해서 매번 전체 순회 -> 30 * 100,000 개 시간 복잡도 OK
    list<string> cache;
    for(int i=0; i< cities.size(); i++){
        string city_name = cities[i];
        transform(city_name.begin(), city_name.end(),city_name.begin(),::toupper);
        auto cn = find(cache.begin(),cache.end(),city_name);
        if (cacheSize == 0){
            answer+= 5;
        } else if (cn == cache.end()){//cache miss
            if (cache.size() == cacheSize)
                cache.pop_front();
            cache.push_back(city_name);
            answer+=5;
        }else{ // cache hit
            cache.erase(cn);
            cache.push_back(city_name);
            answer++;
        }
    }
    return answer;
}

 

문제 풀이의 흐름

간단하다 직접 캐시에 넣고 빼고 할 수 있는지를 묻는 문제이다.

크게 4가지로 나뉜다.

1. 캐시가 가득 찼을 때 캐시 히트 : 캐시의 히트된 녀석을 가장 최근에 히트된 걸로 업데이트

2. 캐시가 가득 찼을 때 캐시 미스 : 캐시의 가장 앞을 없애고 가장 뒤에 미스된 걸 채우기

3. 캐시가 가득차지 않았을 때 캐시미스 : 캐시의 가장 뒤에 새로운 걸 넣기

4. 캐시가 가득차지 않았을 때 캐시 히트 : 히트된 녀석을 가장 최근에 히트된 값으로 넣기.

 

사실상 구현문제

주의 할 점

대소문자를 구분하지 않으니 잘 생각해보자.

어떤 자료구조를 선택할지에 대해서 잘 생각하는게 이 문제의 출제의도인 것 같다.

이걸 어떤 자료구조로 할까 고민하다가

크게 맵을 2개를 사용해서 하는 방법과

리스트를 쓰는 방법을 고민했지만 사실 갯수가 30개 밖에 되지 않기 때문에 중간에 삽입이 편리한 리스트를 사용해서 문제를 해결했다.

많은 사람들이 벡터를 쓰는데 이는 사실 o(n)이 소요되기 때문에 면접때 물어볼수도 있지 않을까..?

 

반성 및 고찰

초기에는 이 코드로 문제를 풀려고 했다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    map <string, int> M; //도시이름, 몇번째 인덱스에 등장했는지 
    for(int i=0; i< cities.size(); i++){
        string city_name = cities[i];
        transform(city_name.begin(), city_name.end(),city_name.begin(),::toupper);
        // cout << city_name <<"\n";
        if (M.find(city_name) == M.end()){ //처음 등장하는 경우
            answer+=5;
        } else {
            if (i - M[city_name] <= cacheSize){ //캐시 히트
                answer+=1;
            } else {
                answer+=5;
            }
        }
        M[city_name] = i;
    }
    return answer;
}

얼핏 보기에는 문제가 없어보인다.

캐시 히트를 판별하는 부분에서 

i - M[city_name] <= cacheSize  

를 기준으로 캐시를 히트 한다고 생각했기 때문이다.

하지만 아래 반례가 있다.

캐시 크기: 3
도시 배열: ["Jeju", "Pangyo", "Seoul", "Pangyo", "Jeju"]
올바른 LRU 캐시 시뮬레이션

i = 0: "Jeju" → 미스 (캐시: [Jeju], 실행시간 5)
i = 1: "Pangyo" → 미스 (캐시: [Jeju, Pangyo], 실행시간 5)
i = 2: "Seoul" → 미스 (캐시: [Jeju, Pangyo, Seoul], 실행시간 5)
i = 3: "Pangyo" → 히트 (캐시 순서 업데이트: [Jeju, Seoul, Pangyo], 실행시간 1)
i = 4: "Jeju" → 히트 (캐시: [Seoul, Pangyo, Jeju], 실행시간 1)
총 실행시간: 5 + 5 + 5 + 1 + 1 = 17

 

제공된 코드 동작
i = 0 ~ 2: "Jeju", "Pangyo", "Seoul" → 모두 미스
i = 3: "Pangyo" → 이전 등장 인덱스가 1, 3−1=2≤3 이므로 히트
i = 4: "Jeju" → 이전 등장 인덱스가 0, 4−0=4>3 이므로 미스로 처리
총 실행시간: 5 + 5 + 5 + 1 + 5 = 21