[프로그래머스] [1차] 캐시

캐시

지도개발팀 상황
제이지 ) 지도에서 도시 이름 검색 -> 맛집 게시물을 db에서 읽어 보여줌
어피치 ) 각 로직 성능 측정 -> db 가져오는 실행시간 오래 걸림
제이지 ) 캐시 크기 얼마 good?

db 캐시 적용 시 캐시 크기에 따른 실행시간 측정

형식
캐시 크기 cacheSize 정수 0~30, 도시 이름 배열 cities 최대 100,000개
각 도시 이름은 영문자로만 구성, 대소문자 구분x, 최대 20자

답 ) 총 실행 시간

조건 ) 
캐시 교체 알고리즘 : LRU Least Recently Used
cache hit : 1
cache miss : 5

LRU 알고리즘 )
가장 오랫동안 참조되지 않은 페이지 교체

예시
cacheSize : 3, cities = [제주, 판교, 서울, 뉴욕, LA, 제주, 판교, 서울, 뉴욕, LA]

제주 | 판교 | 서울 | 뉴욕 | LA | 제주 | 판교 | 서울 뉴욕 LA
5 * 10 = 50

예시2
cacheSize : 3, cities = [제주, 판교, 서울, 제주, 판교, 서울, 제주, 판교, 서울]

제주 판교 서울 5 * 3
판교 서울 제주 + 1
서울 제주 판교 + 1
제주 판교 서울 + 1
판교 서울 제주 + 1
서울 제주 판교 + 1
제주 판교 서울 + 1 = 21

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    
    if (cacheSize == 0)
        return (cities.size() * 5);
    
    for (int i = 0; i < cities.size(); i++){
        for (char& c : cities[i]) {
            if (isupper(c))
                c = tolower(c);         
        }

        auto it = find(cache.begin(), cache.end(), cities[i]);
        
        if (it != cache.end()) {
            cache.erase(it);
            cache.push_back(cities[i]);
            answer++;
        }
        else {
            if (cache.size() >= cacheSize)
                cache.erase(cache.begin());
            cache.push_back(cities[i]);
            answer += 5;
        }
        
    }
    return answer;
}

 

처음에 cacheSize가 0일 때를 고려하지 못했었다.

그러니 else문의 if문에서 cache.erase(cache.begin()); 에서 에러가 나서 제일 처음으로 고려를 해주었다.

 

생각보다 쉽게 풀려서 점수가 낮을 줄 알았는데 9점을 얻은 것이 의외다..