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

---

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    vector<string> cache;
    
    for(auto &city : cities){
        transform(city.begin(), city.end(), city.begin(), ::tolower);
        
        auto it = find(cache.begin(), cache.end(), city);
        
        if(it != cache.end()){
            answer += 1;
            
            rotate(cache.begin(), it, it + 1);
        }else{
            answer += 5;
            
            cache.insert(cache.begin(), city);
            
            if(cache.size() > cacheSize){
                cache.pop_back();
            }
        }
    }
    
    return answer;
}

---

📝 풀이

이 문제를 풀기 위해서 LRU 알고리즘에 대해 알아야 한다.

LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다.

 

입출력 예제 #2 cacheSize = 3, cities = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]

입력	cache hit / miss	cache memory	time
Jeju	miss	Jeju	+5
Pangyo	miss	Jeju, Pangyo	+5
Seoul	miss	Jeju, Pangyo, Seoul	+5
Jeju	hit	Jeju, Pangyo, Seoul	+1
Pangyo	hit	Pangyo , Jeju , Seoul	+1
Seoul	hit	Seoul , Pangyo , Jeju	+1
Jeju	hit	Jeju, Seoul , Pangyo	+1
Pangyo	hit	Pangyo, Jeju, Seoul	+1
Seoul	hit	Seoul, Pangyo, Jeju	+1

 

입출력 예제 #5 cacheSize = 2, cities = ["Jeju", "Pangyo", "NewYork", "newyork"]

입력	cache hit / miss	cache memory	time
Jeju	miss	Jeju	+5
Pangyo	miss	Jeju, Pangyo	+5
NewYork	miss	NewYork, Jeju	+5
newyork	hit	NewYork, Jeju	+1

 

cache hit는 cache memory에 입력한 값이 존재 할 때이고, miss는 존재하지 않을 때이다.

hit일 때는 입력한 값을 cache memory의 헤드로 옮기고 나머지 데이터는 뒤로 하나씩 밀린다.

miss일 때는 cache memroy의 헤드에 새롭게 추가하고 나머지 데이터는 뒤로 하나씩 밀린다.

추가로 cacheSize를 넘지 않는지도 확인해야 한다. (지금 보니 miss인 경우 코드가 번거롭게 작성됐다😅)

 

hit과 miss의 경우에 걸린 실행 시간을 더하여 계산하여 return하면 끝.

문제 풀 때 추가로 주의할 점은 대소문자를 구분하지 않는 점을 명심!! 입출력 예제 #5 참고

 

⭐ cache memory의 head에 채워넣어야 하기 때문에 실제 LRU 알고리즘 구현에는 vector보다 연결 list가 적합하다.