[알고리즘 TIL] 캐시(Java, 자료구조)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java

프로그래머스

프로그래머스 LV2. 자료구조

트러블 슈팅

페이지 교체 알고리즘 중 하나인 LRU를 이용해 푸는 문제이다. 하지만 LRU를 LFU와 헷갈려서 참조 횟수를 기반으로 구현하다가 오류가 났다. 이 기회에 페이지 교체 대표 알고리즘 3개에 대해 알아보았다.

• FIFO(First In First Out): 메모리에 가장 오래 있던 페이지를 교체
• LRU(Least Recently Used): 가장 오랫동안 사용되지 않았던 페이지를 교체
• LFU(Least Frequently Used): 참조된 횟수가 가장 적은 페이지를 교체

LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이므로, Queue 자료구조를 활용하여 FIFO 방식으로 교체하되, 페이지가 참조되면 Queue의 맨 뒤에 다시 적재하는 로직을 추가하였다.

 

간단해보이는 문제일지라도, 적절한 자료구조를 선택하여 풀어야한다.

구현

static class Solution {
        public int solution(int cacheSize, String[] cities) {
            int answer = 0;
            ArrayDeque<String> cache = new ArrayDeque<>();
            for (String city : cities) {
                city = city.toLowerCase();
                if(cache.contains(city)){
                    answer++;
                    cache.remove(city);
                    cache.add(city);
                } else {
                    answer+=5;
                    cache.add(city);
                    if(cacheSize<cache.size()) cache.poll();
                }
            }
            return answer;
        }
    }