코딩 테스트

(Java) 프로그래머스 캐시

로승리 2022. 4. 28. 00:26

처음에는 Queue로 접근해야 하나 고민했다.

그런데 문제에 캐시 교체 알고리즘이 LRU라고 쓰여있는 걸 보고 처음 보는 알고리즘이라

찾아보니 LinkedList가 기반인 알고리즘이었다.

그래서 조금 더 생각해보니 Queue가 아니라 LinkedList로 구현하는 게 훨씬 쉽겠다 싶었다.

어렵지 않게 작성하여 통과했다.


최종코드

import java.util.LinkedList;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        // cities 값을 소문자로 변환
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase();
        }
        LinkedList<String> list = new LinkedList<>();
        // 캐시의 사이즈가 0일수도 있다는것을 고려
        for (int i = 0; i < cities.length; i++) {
            if(list.size() > cacheSize) {
                list.removeLast();
            }
            // Hit인경우
            if(list.contains(cities[i])) {
                list.remove(list.indexOf(cities[i]));
                answer++;
            // Miss인경우
            } else {
                answer+=5;
            }
            list.addFirst(cities[i]);
        }
        return answer;
    }
}