[프로그래머스,자바] Level2: 캐시

문제분석

 

이 문제같은경우는,  정보처리기사 지식을 요구하는 문제입니다.

혹여나 시험보다가 모르겠다하면 인터넷 검색하면 물론 나오긴합니다.

 

 

문제에서는 캐시 교체(페이지 교체)알고리즘인 LRU를 사용하라고 하엿습니다.

 

LRU가 도대체 뭐길래?

 

Least Resently Used로 가장 최근에 썻던걸 쓰겠다란 말인데..

 

이걸 반대로생각하셔야합니다. 가장 최근에 있는걸 쓴다는건, 가장 안쓰는건 먼저 삭제가됩니다.

 

처음 문제를 접할때 또한 cache hit 과 cache miss입니다.

 

cache miss란 주어진 캐시크기 안에 해당 정보가 없으면 Miss가 발생합니다.

 

cache hit이란 주어진 캐시크기 안에 해당 정보가 있으면 Hit이 발생합니다.

 

즉, 캐시크기는  리스트의 사이즈입니다. 

 

 

예시를 한번 보겠습니다.

 

캐시크기 3이고 리스트가 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 입니다

 

먼저 , 제주 판교 서울은  캐시크기안에 저장되어있지않으니 Miss가 3번 일어납니다.

->현재 리스트상태 [제주,판교,서울]

 

그리고 뉴욕 데이터가 들어오는데, 뉴욕은 캐시에 없으니 Miss가 일어납니다.

하지만, 캐시크기가 꽉차있기때문에 교체알고리즘 LRU를 사용합니다.

앞서 말했듯이, 가장 안쓰는게 먼저 삭제가됩니다.  제일 먼저들어온 제주가 삭제댑니다.

->[판교,서울,뉴욕]

 

그다음엔 LA가 들어오는데 역시 캐시에없으니 Miss가 일어나고 LRU로인해, 가장 안쓴 판교가삭제가됩니다.

->[서울,뉴옥,LA]

 

... 반복하다보면 모든 요소가 Miss가 일어나 50이 반환이됩니다.

 

그리고 Cache Hit일땐,  hit당한 요소를 삭제하고 다시 넣어주셔야합니다.

왜냐하면 hit를 햇다는건 그 자원을 썻다는 말이며, 가장 최근 사용한 값이기때문이죠.

 

 

여기서 LRU의 대해 삭제대는 요소들은 하나같이, 가장 먼저들어온게 가장 먼저 삭제가됩니다.  

 

네 바로 FIFO 선입선출인 Queue를쓰기 아주 적합합니다.

 

 

푸는법을 알았으니 나머지는 코드화 시키시면 됩니다.

문제풀이

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> que = new LinkedList<>();
        if(cacheSize==0){
            return cities.length*5;
        }        
        for(String data:cities){
            data=data.toLowerCase();
            //hit 되면 최신값으로 바꾸기
            if(que.contains(data)){
                answer++;
                que.remove(data);                
            }
            else{
                answer+=5;
                if(que.size()==cacheSize){
                    que.remove();               
                }
            }
            que.add(data);
        }      
        return answer;
    }
}