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

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

import java.util.List;
import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        // 캐시 사이즈가 0이라면 DB접속 계속 해야함
       if(cacheSize == 0) {
           return cities.length * 5;
       }
        
        int answer = 0;
    
        List<String> caches = new LinkedList<>();
        for(int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase(); // 대소문자 구분x
            // cache에 없다면
            if(!caches.contains(city)) {
                answer += 5;
                if(caches.size() >= cacheSize) {
                    // 가장 앞에 있는 것이 오랫동안 사용하지 않은 캐시
                    caches.remove(0);
                }
                caches.add(city);
                continue;
            }
            // cache에 있다면
            else {
                answer += 1;
                // 리스트에서 삭제시키고 다시 추가
                // 맨 뒤가 가장 최근에 찾은 도시가 되고, 가장 앞이 삭제 대상
                caches.remove(city);
                caches.add(city);
            }
        }
        
        return answer;
    }
}

• LRU 알고리즘(Least Recently Used) : 가장 오랫동안 사용되지 않은 캐시 교체

  • 메모리에 남아 있는 캐시 중 가장 오래동안 사용되지 않은 캐시를 새로운 캐시로 교체
  • cache fault 발생
    • 캐시가 꽉 차있는 상태 : 가장 오랫동안 사용하지 않은 데이터 삭제
      • list.remove(0)로 가장 앞에 있는 데이터 삭제
    • 캐시가 꽉 차있지 않다면 : 데이터 추가
  • cache hit : 가장 최근에 참조한 데이터로 순서를 변경해야 하니,
    리스트에서 삭제했다가 다시 추가해준다.(이러면 항상 마지막이 최근, 가장 맨 앞이 가장 오래전 참조)

• 동작 방식
  

• 출처 : [Java/자바] 프로그래머스 Lv2 - [1차]캐시 (LRU 알고리즘)