프로그래머스 - [1차] 캐시 (Lv.2)

문제 링크

• 1차 캐시

문제 접근

• map 자료구조는 key를 기준으로 오름차순 혹은 내림차순 정렬이 가능하다.
• 따라서, key를 city로 두는 경우 참조가 오래된 순서로 정렬이 되는 것이 아닌 도시 이름 순으로 정렬이 된다.
• map을 value 를 기준으로 정렬하는 방법으로 정렬용 vector 컨테이너를 선언하여 map을 인자로 넣어주는 방법이 있다.

구현(All Pass)

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cctype>

using namespace std;

void set_to_lower_case(vector<string>& cities){
    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]);
        }
    }
}

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

int solution(int cacheSize, vector<string> cities) {
    int run_time = 0;    
    if(cacheSize==0) {
        run_time = cities.size() * 5;
        return run_time;
    }
    
    set_to_lower_case(cities);
    
    map<string, int> cache;
    for(int i=0; i<cities.size(); i++){
        // cache에 없는 경우(miss) 실행시간 5 증가
        if(cache.find(cities[i])==cache.end()){
            if(cache.size()==cacheSize){
                // map의 value를 기준으로 정렬한 후 city를 찾는다.
                vector<pair<string, int>> v(cache.begin(), cache.end());
                sort(v.begin(), v.end(), cmp);
                cache.erase(v[0].first);
            }
            run_time += 5;
            cache[cities[i]]=i;
        }
        else { // cache에 있는 경우(hit) 실행시간 1 증가
            run_time++;
            cache[cities[i]]=i;
        }
        
    }
    
    return run_time;
}