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

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

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

<풀이>

1. 각 도시이름을 캐시에 넣는다.

2. LRU 알고리즘에 따라, 캐시를 교체하고 실행시간을 갱신한다.

3. 총 실행시간을 반환한다.

 

<해법>

1. 캐시 구현 방법

=> 저는 deque를 이용하여 캐시를 구현하였습니다. 또한 가장 오래전에 사용된 값은 덱의 맨 앞에, 가장 최근에 사용된 값은 덱의 맨 뒤에 저장하였습니다. 덱을 사용한 이유는, 교체될 덱의 맨 앞의 값을 pop_front() 함수를 써서 쉽게 빼기 위함입니다.

 

2. 캐시 교체 방법

 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
 
using namespace std;
 
int solution(int cacheSize, vector<string> cities) {
 
    int answer = 0;
 
    //pop_front()를 사용하기 위해 deque를 사용
    deque<string> cache;
 
    for (int i = 0; i < cities.size(); i++) {
 
        //캐시에 넣어야 할 도시
        string city = cities[i];
 
        //대문자 -> 소문자 변환
        for (int j = 0; j < city.length(); j++) {
            city[j] = tolower(city[j]);
        }
 
        //캐시 hit, miss인지 판단
        bool hit = false;
        int index = 0;
        for (index = 0; index < cache.size(); index++) {
            if (cache[index] == city) {
                hit = true;
                break;
            }
        }
 
        //일단 cache 가장 뒤에 넣기(LRU 이므로)
        cache.push_back(city);
 
        //캐시 hit일 경우
        if (hit) {
            //캐시에 있는 기존 데이터 삭제
            cache.erase(cache.begin() + index);
            answer += 1;
        }
        //캐시 miss일 경우
        else {
            //캐시가 넘쳤을 경우, 맨 앞에 있는 가장 오래된 데이터 삭제
            if (cache.size() > cacheSize) {
                cache.pop_front();
            }
            answer += 5;
        }
    }
 
    //결과 반환
    return answer;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.