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

문제

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

코딩테스트 연습 - [1차] 캐시

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

cache hit일 경우 실행시간은 1이다.

cache miss일 경우 실행시간은 5이다.

 

풀이

LRU 알고리즘은 사용한 지 가장 오래된 페이지를 대체하는 방법이다. 

자료구조는 LinkedList를 사용하였다.

 

cache size가 0일 때는 city를 처리하는데는 city개수 * 5 의 처리 시간이 걸린다.

cache size가 0보다 큰 경우 

- 캐시에 현재 데이터가 없다면? 

  : 캐시가 꽉 찼다면 사용한지 가장 오래된 데이터를 삭제한다 

  : 현재 데이터를 넣는다

- 캐시에 현재 데이터가 존재한다면?

  : 해당 데이터를 삭제하고 가장 최신 위치에 다시 넣는다.

 

소스코드

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        // LRU
        // 사용한지 가장 오래된 페이지를 대체
        LinkedList<String> list = new LinkedList<String>();
        if(cacheSize == 0){
            return 5*cities.length;
        }
        for(String city : cities){
            city = city.toUpperCase();
   
            if(list.contains(city)){
                answer += 1;
                list.remove(list.indexOf(city));
                list.offer(city);
            } else {
                if(list.size() == cacheSize){
                    list.poll();
                }
                answer += 5;
                list.offer(city);
            }
        }
            
            
        return answer;
    }
}