[자바] [1차] 캐시

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

프로그래머스

캐시 교체알고리즘 중 LRU 알고리즘 (가장 오랫동안 참조되지 않은 페이지를 교체하는 기법)을 사용하고, cache miss와 cache hit에 따라 점수를 계산해야 한다.

 

여기서 핵심은 LRU알고리즘을 알아야한다. 

1. 현재 데이터가 캐시에 있다 -> 캐시에 있는 데이터는 지우고, 새로운 캐시를 넣어야한다 (참조한 페이지는 remove하고 새로 페이지를 add한다)

* 이때, poll()을 사용하면 안된다. 왜냐면, 이 페이지를 참조했는지를 알기 위해선 quque에 앞쪽에는 오랫동안 참조되지 않은 것 ~ 뒤쪽은 최근 데이터 순으로 들어가야한다. 그래서, 참조를 했다면 참조함을 표시하기 위해 해당 데이터를 없애고, 새 최근 데이터로 뒤쪽에 add를 한다. 

즉, [A,B,C]가 있을 때, A데이터가 있다면 [A,B,C]가 아닌, [B,C,A]형태로 들어간다!

 

 

2. 현재 데이터가 캐시에 없다 -> 아직 캐시가 차지 않았다면 추가만 하고, 캐시가 찼고, 여기에 없는 새로운 데이터라면 가장 오랫동안 참조되지 않은 페이지(맨 앞(queue의 poll))을 빼고, 새롭게 넣는다. 

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> q = new LinkedList<>();
        if (cacheSize==0) {
            answer=cities.length*5;
            return answer;
        }
        
        for (int i=0; i<cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
            if (q.contains(cities[i])) {
                q.poll();
                q.add(cities[i]); 
                answer++;
            }
            else {
                if (q.size()!=cacheSize) {
                    q.add(cities[i]);
                }
                else {
                    q.poll();
                    q.add(cities[i]);
                }
                answer+=5;
            }
        
        }
        return answer;
    }
}