2018 KAKAO BLIND 캐시 (Java)

Problem

• 문제 링크

LRU 캐시 교체 알고리즘(Least Recently Used)을 구현하면 됩니다.

Solution

LRU 알고리즘이란 가장 오랫동안 사용되지 않은 데이터를 교체하는 겁니다.

크기가 3 인 캐시에 [1, 2, 3, 1] 순서로 데이터가 들어갔다면 1 이 가장 오래된 데이터지만 가장 오랫동안 사용되지 않은 데이터는 2 입니다.

따라서 새로운 데이터 4 가 들어간다면 2 를 삭제하고 [3, 1, 4] 가 남게 됩니다.

LinkedHashSet 자료구조를 사용하여 구현하였습니다.

LinkedHashSet 은 HashSet 과 동일하게 삽입/검색/삭제 시간복잡도가 O(1) 이지만 내부적으로 연결리스트를 사용하여 순서가 보장됩니다.

캐시 안에 이미 도시 이름이 존재하면 기존에 있는 걸 삭제 후 다시 add 하여 갱신해줍니다.

캐시 안에 도시 이름이 존재하지 않으면 새로 추가합니다.

set.size() 가 cacheSize 를 넘어버린다면 가장 오랫동안 사용되지 않은 값을 삭제합니다.

삽입/삭제 구현 방식에 따라서 LinkedHashSet 의 첫번째 인덱스가 사용되지 않은 값이므로 set.iterator().next() 를 통하여 데이터를 가져와 삭제합니다.

Java Code

import java.util.*;

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

        return answer;
    }
}