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

프로그래머스 캐시

문제풀이

구현은 어렵지 않은 문제였으나 LRU(Least Recently Used)에 대해서 알고있어야지만 풀 수 있는 문제였다. LFU와 헷갈려서 문제푸는데 시간이 조금 더 걸렸다.

• LRU(Least Recently Used)
  가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.
• LFU(Least Frequently Used)
  가장 적게 참조한 페이지를 캐시에서 교체하는 것이다.
  

LRU 알고리즘을 구현하면 되는데 자료구조 Queue를 사용하면 편하다. Java에서는 LinkedList가 Queue의 구현체이므로 그냥 LinkedList를 사용했다.

• 캐시 적중
  • 이미 캐시에 있던 페이지를 가장 처음으로 가져온다.
    기존에 있던 페이지를 지우고 Queue의 가장 처음에 삽입하면 된다.
• 캐시 미스
  • 캐시가 가득 찬 경우
    가장 뒤(참조한지 가장 오래된)의 페이지를 삭제하고 가장 앞에 새 페이지를 삽입한다.
  • 캐시에 자리가 있는 경우
    가장 앞에 새 페이지를 삽입한다.

이 문제의 경우에 캐시사이즈가 0인 경우도 주어지는데 그 때를 따로 핸들링 해줘야한다.

• 캐시 사이즈가 0일때는 모든 경우에 캐시 미스가 발생하기 때문에 총 페이지 수 * 5를 반환한다.

구현코드

import java.util.*;

class Solution {
    
    static final int CACHE_HIT = 1;
    static final int CACHE_MISS = 5;
    
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) return 5 * cities.length;
        
        int answer = 0;
        
        LinkedList<String> cache = new LinkedList<>();
        
        for(int i = 0 ; i < cities.length ; ++i){
            String city = cities[i].toUpperCase();
            
            // cache hit
            if(cache.remove(city)){
                cache.addFirst(city);
                answer += CACHE_HIT;
            
            // cache miss
            } else {
                int currentSize = cache.size();
                
                if(currentSize == cacheSize){
                    cache.pollLast();
                }
                
                cache.addFirst(city);
                answer += CACHE_MISS;
            }
        }
        return answer;
    }
}