프로그래머스[LEVEL2] - 캐시(2018 카카오 블라인드 코딩테스트)

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

프로그래머스

 

 

 

 

 

 

 

 

 

 

   

문제 풀이 

 

  

   

 

    이 문제의 핵심 페이지 교체알고리즘인 LRU에 대해서 알아야 접근할 수 있는 문제이다 

    

    https://gomguard.tistory.com/115

페이지 교체 알고리즘 - LRU

  

LRU란 쉽게 말하면 페이지에서 새로운 값이 들어와 제거해야 할때 가장 오랫동안 사용하지 않은 것을 

제거하겠다는  알고리즘이다.

 

예를 들어보면 cities가 ["Jeju", "Pangyo", "Seoul", "Pangyo", "Seoul"] 이고 cacheSize가 2인 경우 처음 Jeju와 Pangyo 는 buffer에 아무것도 없기 때문에 push한다 이때 캐시에 이미 존재하는 경우 cache hit라 playtime에는 1을 증가시키고 캐시에 존재하지 않는 경우 cache miss로 playtime을 5로 증가시킨다 Jeju와 Pangyo  같은 경우 cache miss이므로 playtime에는 각각 +5 를 한다 .

 

그리고 다음 데이터로 Seoul이 왔을때 cacheSize는 2인데 cache가 이미 2개의 데이터를 갖고 있으므로 하나의 데이터를 제거하고 Seoul을 push해야 되는데 이때 제거되는 것이 Jeju이다 캐시에 들어오고 가장 오랫동안 재사용되지 않았기 때문이다 Jeju를 제거하고 Seoul을 push한다 이때도 cache miss 이므로 playtime += 5 를 한다.

 

그 다음 Pangyo 가 오는데 이미 cache에는 Pangyo 가 있다 따라서 이때는 cache hit다 따라서 playtime += 1을 해준다 

그리고 Pangyo를 splice로 제거하고 cache에 Pangyo를 push 한다 왜냐면 가장 최근에 사용된 캐시이기 때문에 가장 마지막 인덱스로 보내준다 마지막 Seoul도 마찬가지다 즉  playtime은 결국 17이다