[프로그래머스] - [1차] 캐시(Java)

[1차] 캐시

Solution

LRU(Least Recently Used) Algorithm : 가장 오래 참조되지 않은 페이지를 교체하는 기법

Queue는 중간에 있는 값을 삭제할 수 없기 때문에 LinkedList를 사용하여 구현하였다.

• cache hit

  • 실행시간 1초
  • 캐시 크기에 상관없이 도시 갱신

• cache miss

  • 실행시간 5초
  • 캐시에 여유가 있다면 도시 추가, 여유가 없다면 가장 오래 참조하지 않은 도시 삭제 후 추가

Code

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        if(cacheSize == 0)
            return cities.length * 5;
        
        int answer = 0;
        LinkedList<String> list = new LinkedList<>();
        
        for(String city : cities){
            String cityName = city.toLowerCase();
            int idx = list.indexOf(cityName);
          
            if(idx >= 0){
                answer += 1;
                list.remove(idx);
            }
            else{
                answer += 5;
                if(list.size() >= cacheSize){
                    list.remove(0);
                }
            }
            list.offer(cityName);
        }
        return answer;
    }
}