Programmers 17680 캐시

20 Apr 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680

나의 풀이

대소문자 구분이 없기 때문에 모든 문자열을 대문자로 변환한다.
캐시에 문자열별 지난 시간을 기록하며, cache hit일 경우 지난 시간을 0으로 초기화하고 실행시간을 1증가 시킨다.
cache miss인 경우 실행시간 5를 증가시키고, 지난 시간이 가장 큰 문자열을 캐시에서 뺀다.

풀이 코드 : 17680 캐시

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    if(cacheSize == 0) return cities.size()*5;
    int answer = 0;
    bool find;
    vector<pair<int, string>> cache;
    for(int i=0;i<cities.size();i++) {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::toupper);
    }
    for(int i=0;i<cities.size();i++){
        find = false;
        for(int j=0;j<cache.size();j++){
            cache[j].first += 1;
            if(cache[j].second == cities[i]){
                find = true;
                answer+=1;
                cache[j].first = 0;
            }
        }
        if(find == false){
            answer += 5;
            if(cache.size() != 0 && cache.size() >= cacheSize){
                sort(cache.begin(), cache.end());
                cache.pop_back();
            }
            cache.push_back(make_pair(0, cities[i]));
        }
    }
    return answer;
}

채점결과