[Java]프로그래머스 Lv2_[1차]캐시 ( LRU, LinkedHashMap)

📌 개인적인 공간으로 공부를 기록하고 복습하기 위해 사용하는 블로그입니다.
정확하지 않은 정보가 있을 수 있으니 참고바랍니다 :😸
[틀린 내용은 댓글로 남겨주시면 복받으실거에요]

프로그래머스 Lv2. 1차 캐시

풀어보기🔗: [1차]캐시

문제 풀이

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(String c : cities) {
            map.put(c, map.getOrDefault(c, 0) + 1 );
        }
        
        List<String> list = new ArrayList<>(map.keySet());
        
        //value 내림차순으로 정렬
        list.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
        
        
        //역순으로 정렬 했을 때 캐시 내는 1 , 아니면 5인데
        //map에 개수-1 만큼 저장되어있으니까
        //value * 실행시간
        
        List<String> hit = new ArrayList<>();
        
        // cache hit
        for(int i = 0 ; i < cacheSize ; i++) {
            hit.add(list.get(i));
        }
        
        for(String s : map.keySet()) {
           if(hit.contains(s)) {
               answer += map.get(s) * 1;
           } else {
               answer += map.get(s) * 5;
           }
        }
        
        return answer;
    }
}

이렇게 풀었는데 테스트 코드 실행하니까 다 틀렸고,, 내가 생각한 계산과는 일치해서 LFU를 몰라서 틀리는 이유 같았다. 검색해도 이해가 잘 안 가서 가지고 있는 CS 책 찾아봤는데 거기에도 LFU는 없는…ㅠㅠㅠ…

내가 대충 이해하기로는 오래 사용하지 않는 걸 먼저 제거한다는 뜻인 것 같은데 아무래도 캐시가 꽉 찬 경우 가장 오래된 데이터를 제거하는 로직으로 이해했다.

그래서 현재 map 구조에서 LinkedHashMap 구조를 사용해주어야 한다 (자바의 정석에서 아래 내용을 쪼그맣게 찾아볼 수 있었다..)

Set이 아닌 Map을 사용 해야 하는 이유

• LinkedHashSet도 있지만, Set은 순서를 보장하지 않으므로, 가장 오래된 항목을 찾거나 삭제할 수 없다.
• 또한 캐시 크기 제한을 구현 하기 어려움 > 캐시 크기 초과 시 오래된 항목을 자동으로 삭제하는 기능이 없다.

LinkedHashMap, LinkedHashSet HashMap과 HashSet에 저장 순서 유지 기능을 추가

LinkedHashMap 이란?

아래의 경우에 주로 사용된다.

• LRU 캐시 구현: 제한된 크기의 캐시에서 가장 오래된 항목을 교체해야 하는 경우
• 순서 기반 데이터 저장: 삽입 순서나 접근 순서에 따라 데이터를 관리해야 하는 경우

생성

1. 기본 생성

    LinkedHashMap<K, V> map = new LinkedHashMap<>();
   

2. 초기 용량, 부하율 설정 생성자

    LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity, float loadFactor);
   

3. 접근 순서 설정 생성자

    LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity, float loadFactor, boolean accessOrder);
   

   • initialCapacity: 초기 용량 (기본값 16)
   • loadFactor: 부하율, 용량이 초과되기 전에 버킷을 재조정하는 비율 (기본값 0.75)
   • accessOrder가 true이면 접근 순서를 유지합니다. 즉, 가장 최근에 접근한 엔트리가 뒤로 이동
   • false일 경우 기본적으로 삽입 순서를 유지

LRU 구현의 핵심: removeEldestEntry

LinkedHashMap을 사용하면, removeEldestEntry(Map.Entry<K,V> eldest) 메서드를 오버라이드하여 가장 오래된 항목(즉, 처음에 삽입된 항목)을 삭제하는 조건을 정의할 수 있다.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cacheSize;

    public LRUCache(int cacheSize) {
        super(cacheSize, 0.75f, true); // 접근 순서를 유지
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize; // 캐시 크기를 초과하면 가장 오래된 항목 삭제
    }
}

• size() > cacheSize: 현재 캐시 크기가 제한 크기를 초과하면 true를 반환하여 가장 오래된 항목을 제거한다.
• 이렇게 하면 캐시가 항상 제한된 크기를 유지하면서 LRU 동작을 구현할 수 있다.

예제

1. LRU : removeEldestEntry 활용

    import java.util.LinkedHashMap;
    import java.util.Map;
       
    public class LRUExample {
        public static void main(String[] args) {
            Map<Integer, String> cache = new LinkedHashMap<>(3, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
                    return size() > 3; // 3개 초과 시 가장 오래된 항목 제거
                }
            };
       
            cache.put(1, "A");
            cache.put(2, "B");
            cache.put(3, "C");
       
            System.out.println(cache); // 출력: {1=A, 2=B, 3=C}
       
            cache.get(1); // 1번 접근
            cache.put(4, "D"); // 캐시 크기 초과 -> 가장 오래된 2번 제거
       
            System.out.println(cache); // 출력: {3=C, 1=A, 4=D}
        }
    }
   

   • 캐시가 3개를 초과하면 가장 오래된 항목을 제거
   • get(1)을 호출했으므로, 1번이 가장 최근에 접근된 항목으로 이동
   • 4번을 추가하면, 가장 오래된 2번이 제거된다.

2. LRU 와 FIFO

    import java.util.LinkedHashMap;
       
    public class TestLinkedHashMap {
        public static void main(String[] args) {
            // LRU: 접근 순서 유지
            LinkedHashMap<Integer, String> lru = new LinkedHashMap<>(3, 0.75f, true);
       
            // FIFO: 삽입 순서 유지
            LinkedHashMap<Integer, String> fifo = new LinkedHashMap<>(3, 0.75f, false);
       
            lru.put(1, "A");
            lru.put(2, "B");
            lru.put(3, "C");
            lru.get(1); // 접근 순서 갱신
       
            fifo.put(1, "A");
            fifo.put(2, "B");
            fifo.put(3, "C");
            fifo.get(1); // 삽입 순서 유지
       
            System.out.println("LRU: " + lru); // {2=B, 3=C, 1=A}
            System.out.println("FIFO: " + fifo); // {1=A, 2=B, 3=C}
        }
    }
       
   

장점

• 손쉬운 LRU 구현: LinkedHashMap과 removeEldestEntry를 사용하면 간단히 캐시 크기 제한과 LRU 정책을 구현가능
• 효율적: 평균적으로 O(1) 시간 복잡도로 데이터를 검색하고, 추가/삭제할 수 있다.
• 유연성: 삽입 순서와 접근 순서를 자유롭게 설정 가능

LinkedHashSet과 LinkedHashMap 비교

특성	LinkedHashSet	LinkedHashMap
순서 유지	삽입 순서 유지	삽입 순서 또는 접근 순서 유지 (accessOrder)
LRU 구현	수동으로 접근 순서를 관리해야 가능	removeEldestEntry로 간단히 구현 가능
항목 제거	오래된 항목을 직접 찾아 제거해야 함 (Iterator)	자동으로 오래된 항목 제거 가능
구현 복잡성	더 높은 수준의 로직 필요	내장된 기능으로 간단히 처리 가능

Set을 사용할 수 없는 이유를 위에서 잠깐 썼는데 정확히 비교하고 넘어가면 좋을 것 같아서 정리해보았다.

위의 내용을 바탕으로 다시 풀었는데 바로 해결!

정답

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return cities.length * 5;

        int answer = 0;

        Map<String, String> map = new LinkedHashMap<>(cacheSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> old) {
                return size() > cacheSize; 
            }
        };

        for (String city : cities) {
            //대소문자
            city = city.toLowerCase();

            if (map.containsKey(city)) {
                answer += 1;
            } else {
                answer += 5; 
            }
             map.put(city, city); 
        }
        return answer;
    }
}

Programmers 카테고리 내 다른 글 보러가기