[프로그래머스] 캐시 (C++)

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

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

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

#define HIT 1
#define MISS 5

using namespace std;

bool cmp(pair<string,int> p1, pair<string,int> p2){
    return p1.second < p2.second;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<pair<string,int> > cache;
    for (int i=0; i<cities.size(); i++){
        string city="";
        for (char c : cities[i]){
            if (isupper(c))
                city+=(c+32);
            else
                city+=c;
        }
        bool flag=false;
        int cnt=0;
        for (auto& p : cache){
            if (p.first==city){
                answer+=HIT;
                flag=true;
                cache[cnt].second=i;
                break;
            }
            cnt++;
        }
        if (!flag){
            answer+=MISS;
            if (cache.size()==cacheSize){           //빈 공간 없을 때
                if (cacheSize>0){
                    sort(cache.begin(), cache.end(), cmp);
                    cache[0].first=city;
                    cache[0].second=i;
                }
            }
            else{
                cache.push_back({city,i});
            }
        }
    }
    return answer;
}

 

cache hit 일 경우 => cache 벡터를 갱신해주기(이때 갱신이란 pair 값을 i 값(cities에서 순서)으로 변경)

cache miss 일 경우 =>

  빈 공간 없고, cache size가 0이 아닌 경우: cache 벡터를 sorting 한 후 가장 첫번째 값을 해당 city와 i 로 갱신

  빈 공간 있을 경우: cache 벡터에 해당 city, i 를 넣어주기

 

대.소문자 구분 없으므로 city를 소문자나 대문자로 변경해주고 시작해야된다.

 

다른 분들의 코드를 보니 이런 식으로도 소문자 변경이 가능하다.

transform(it->begin(), it->end(), it->begin(), ::tolower);

 

또한 pair를 써줘서 시간을 별도로 갱신할 필요 없이,

vector로 구성해서 hit 된 경우에는 그 값을 erase 하고 다시 그 city를 pushback 해주면 나중에 교체할 대상을 고를때 제일 앞에 있는 애를 erase 해주면 자동으로 LRU 순서대로 빠져나오게 된다.