[Programmers] LV2 - 캐시

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

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

 

문제 파악

 

LRU 캐시 교체 알고리즘을 활용하여 문제 해결을 하자.

Queue를 이용하여 문제를 해결하였다.

 

CacheSize가 0일 경우에는 모든 데이터가 miss 처리 이므로 cities.length * 5를 해서 처리하였고,

 

Queue Size가 CacheSize 만큼 저장되어있지 않다면 Queue에 add 하면서 miss 처리를 하고

Queue Size가 CacheSize와 같을 경우 Queue에 해당 city가 있는지 확인하고 있다면 제거 후 다시 add 하여 맨 뒤로 순서를 조정한다.

 

LRU 캐시 알고리즘에 대해서는 코드가 많이 나오지만 LFU 등 다른 알고리즘은 잘 나오지 않는 것 같다.

한 번 구현을 해보는 것도 좋은 생각일 것 같다.

 

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