[2018 카카오 코딩테스트 1차] 캐시 (C++)

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

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

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    
    if(cacheSize==0) {
        return cities.size()*5;
    }
    
    int answer = 0;

    vector<string> mem;

    for(string city : cities) {
        string s;

        for(int i=0;i<city.length();i++) {
            if(city[i]>='a'&&city[i]<='z') {
                city[i]+=('A'-'a');
            }
            
            s+=city[i];
        }
        // cout<<"city="<<city<<", s="<<s<<endl;

        bool isHit=false;
        int hitIdx=-1;
        for(int i=0;i<mem.size();i++) {
            if(s==mem[i]) {
                isHit=true;
                hitIdx=i;
                break;
            }
        }

        if(isHit) {
            answer+=1;
            mem.erase(mem.begin()+hitIdx);
        }
        else {
            answer+=5;
            if(mem.size()==cacheSize) {
                mem.erase(mem.begin());
            }
        }
        mem.push_back(s);

        // for(int i=0;i<mem.size();i++) {
        //     cout<<"mem"<<i<<":"<<mem[i]<<" ";
        // }cout<<endl;
    }

    return answer;
}

[2018 카카오 코딩테스트 1차] 캐시 (C++)

LRU에 대해 알고 있으면 푸는데 더 도움이 된다.

가장 최근에 사용하지 않은 것은 가장 먼저 퇴출당하는 캐시 교체 알고리즘이다.

사용 횟수와는 상관이 없다.

 

구현 중에 체크할 예외사항

- 도시이름의 대소문자는 구분하지 않기 때문에, 입력받은 cities[] 내용을 소문자 또는 대문자로 통일하자.

- 캐시메모리에 push하기 전에 erase 먼저 해야한다.