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

문제 URL

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

프로그래머스

[문제 설명]

이 문제는 캐시 크기와 도시이름 배열이 주어질 때, 캐시를 통해 배열을 순서대로 처리하는데 걸리는 총 실행시간을 출력하는 문제이다. 

 

문제를 읽어봤는데도 무슨 의미인지 파악하지 못해서 구글링을 해보았다. 내용을 알고보면 어렵지 않은 문제였다.

 

[문제 풀이]

문제에는 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법인 LRU 알고리즘이 사용된다. 

대문자를 모두 소문자로 바꾸어 준 뒤, cities의 원소를 캐시 크기의 vector<string>에 넣어준다.

캐시 크기가 0인 경우는 캐시 hit이 불가능하기 때문에 모든 원소를 cache miss 시킨다. 

cities의 원소가 cache에 이미 있는 경우 LRU를 위해서 캐시에 존재하는 값을 제거 후 벡터의 맨 뒤에 값을 다시 넣어주고,

cities의 원소가 cache에 존재하지 않는 경우 캐시의 맨 앞에 존재하는 값을 제거 후 벡터의 맨 뒤에 값을 넣어준다. 이때, cache가 비어있다면 맨 앞의 값을 제거하는 과정은 생략한다. 

---

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    
    // 캐시 크기가 0
    if(cacheSize == 0){
        answer = cities.size()*5;
        return answer;
    }
    
    for(int i=0; i<cities.size(); i++){
        string check = cities[i];
        transform(check.begin(), check.end(), check.begin(), ::tolower);  // 소문자 변환
        auto address = find(cache.begin(), cache.end(), check);
        
        /*
        리턴 값이 벡터의 end()인 경우 => 해당 원소가 존재하지 않는 것
        리턴 값이 벡터의 end()가 아닌 경우 => 해당 원소 존재하는 것
        */
        
        // 캐시에 있을 경우
        if(address != cache.end()){
            cache.erase(address);
            cache.push_back(check);
            answer++;
            
        }
        // 캐시에 없을 경우
        else{
            // 캐시에 빈자리 있을 때
            if(cache.size() < cacheSize)
                cache.push_back(check);
            // 캐시에 빈자리 없을 때
            else{
                cache.erase(cache.begin());  // 맨 첫 번째 원소 삭제
                cache.push_back(check);
            }
            answer += 5;
        }
    }
    
    return answer;
}