[Algorithm] Programmers_캐시 in Java

💡 Programmers Level.2 캐시:

LRU 알고리즘의 캐시를 활용하여 도시 검색하기

🌱 코드 in Java

알고리즘: Queue

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Set<String> cache = new HashSet<>();
        Queue<String> lru = new ArrayDeque<>(); // lru를 위한 Queue 생성
 
        for (String city: cities) {
            city = city.toLowerCase();
            if (cache.contains(city)) { // city가 cache에 있을 경우
                lru.remove(city); // queue에서 제거 후
                lru.add(city);// 다시 넣어서 뒤로 가도록 함
                answer += 1;
            } else {
                if (cacheSize != 0) { // 캐시를 활용할 수 있을 경우
                    if (cache.size() == cacheSize) { // 캐시가 다 차면
                        String remove = lru.poll(); // 가장 예전에 쓴 도시를 Queue에서 제거
                        cache.remove(remove); // cache에서도 제거
                    }
                    lru.add(city); // lru Queue에 city 넣기
                    cache.add(city); // cache에 추가
                }
                answer += 5;
            }
        }
        return answer;
    }
}

이번 문제는 LRU를 어떻게 구현할까가 관건이었다.
일단 캐시의 경우 Set을 사용해서 검색 시 O(1)의 시간 복잡도를 갖도록 하였고,
LinkedHashSet을 사용하려고 하다가 그냥 Queue를 쓰는 게 더 직관적일 것 같아서 이렇게 짜게 되었다.
Queue에서 remove 메소드가 있는지 모르고 처음에는 이터레이터로 순회하며 일치하는 String을 찾으면 삭제하는 방식을 택했는데 remove 메소드가 있어서 그걸로 변경하였다. remove 내부 구조도 비슷하게 돼있지 않을까 싶다

이렇게 풀고 궁금해서 LinkedHashSet의 경우

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

이렇게 짤 수 있다.

수행시간에 있어서는

1) Queue 활용

2) LinkedHashSet 활용

크게 유의미한 차이는 없으나 Queue가 조금 더 빠른 것을 볼 수 있다.
LinkedHashSet의 경우 해당 객체에 도달하는 시점이 배열보다 느릴 수밖에 없는 것 같다.
내가 Queue에 ArrayDeque를 쓰기도 했고 말이다.

🧠 기억하자

1) queue.remove(object);

• 굳이 순회해서 찾지 않아도 해당 객체를 찾아서 지워준다!