[2018 카카오 블라인드 공채] 캐시 (C++)

2018 카카오 블라인드 공채 1차 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)

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

---

3번 문제 였으며 약 30분 정도 소요되었음.

LRU방식이었으므로 cache에 저장된 문자열만 저장할 것이 아니라, 

각 cache가 언제 사용 되었는지도 저장한다.

cities의 순서대로 진행하면 되는데, cities는 대소문자 구분이 없었으므로 하나로 변환해준다.

그 후, cache에 없으면 사용한지 제일 오래된 (visited_num의 값이 제일 작은) cache를 제거하고 변경하고,

있으면 visited_num의 수를 최신으로 변경해준다.

처음 제출할 때, cachesize가 0일때 고려하지 않아 실패 처리 됐었다.

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    if (cacheSize == 0)
        return 5 * cities.size();

    vector<string> cache(cacheSize);
    vector<int> visited_num(cacheSize, -1);
    vector<string>::iterator it;

    for (int i = 0; i < cities.size(); i++)
    {
        for (int j = 0; j < cities[i].size(); j++)
            if (isupper(cities[i][j]))
                cities[i][j] = tolower(cities[i][j]);

        it = find(cache.begin(), cache.end(), cities[i]);
        if (it == cache.end())
        {
            int min_ind = min_element(visited_num.begin(), visited_num.end()) - visited_num.begin();
            cache[min_ind] = cities[i];
            visited_num[min_ind] = i;
            answer += 5;
        }
        else
        {
            visited_num[it - cache.begin()] = i;
            answer += 1;
        }
    }

    return answer;
}