[Programmers] - 캐시 (Queue)

문제

문제

LRU (Least Recentely Used)

• 즉 없다면 메모리 캐시에 저장하고 사용하지 않는 데이터부터 삭제하고 캐시HIT가 발생하면 다시 가장 최근으로 Update를 해야한다.

풀이

import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;


class Solution {
    public int solution(int cacheSize, String[] cities) {

        int cacheHit = 0;
        int cacheMiss = 0;

        if(cacheSize==0){
            return cities.length * 5;
        }

        Queue<String> cacheList = new LinkedList<>();

        for (String s : cities) {
            String city = s.toLowerCase();

            Optional<String> find = cacheList.stream().filter(c -> c.equals(city)).findFirst();

            if (find.isEmpty()) { // 없다면
                if (cacheList.size() < cacheSize ) {
                    cacheList.offer(city);
                } else {
                    cacheList.offer(city);
                    cacheList.poll();
                }
                cacheMiss++;

            } else {  // 있따면
                cacheList.remove(city);
                cacheList.offer(city);
               

                cacheHit++;
            }

        }

        return cacheHit + 5 * cacheMiss;
    }
}

• LinkedList를 사용한 이유는 ArrayList보다 List의 수정 및 삭제에 알맞는 구조이기 때문
• Queue 형식은 선입선출, 즉 먼저 들어간놈이 먼저 나가는 구조!
• cache에 값이 있다면 이전의 값을 삭제시키고 새로 넣어야 한다(업데이트 하지 않을 시 문제 요구사항에 맞지않음!)
• cache에 값이 없다면 cachesize에 고려하여 그냥 넣을지 아니면 poll(가장 먼저 들어간놈을 빼는 작업 )을 하고 넣을지 수행
• cacheSize가 0 이라면 무조건 cacheMiss이기 때문에 배열 Size * (cacheMiss시 걸리는 시간)을 수행하면 된다.