본문으로 건너뛰기

17680 - [1차] 캐시

정보
  • 문제 보기: 17680 - [1차] 캐시
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: java
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

해시


풀이 코드​

정보
  • 메모리: 91200 KB
  • 시간: 33 ms
import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        Map<String, Boolean> cache = new LinkedHashMap<>(cacheSize+1, 1.0f, true);
        
        // simulate
        if (cacheSize == 0) return cities.length * 5; // corner case
        
        int ans = 0;
        for (int i = 0; i < cities.length; ++i) {
            String keyword = cities[i].toLowerCase();
            if (cache.containsKey(keyword)) { // cache hit
                cache.get(keyword); // trigger accessOrder
                ans += 1;
            }
            else { // cache miss
                if (cache.size() >= cacheSize) { // cache is full -> swap
                    // NoSuchElementException 조심
                    // corner case 처리 안하면 NSEE 발생
                    cache.remove(cache.keySet().iterator().next());
                }
                cache.put(keyword, true);
                ans += 5;
            }
        }
        
        return ans;
    }
}

풀이 해설​

특정 자료구조를 이용하여 LRU를 구현하는 문제이다.


❌ 우선순위 큐는 안돼요​

처음엔 least recent를 pq 우선순위로 판단하려 했는데,

pq는 원소를 하나 꺼내서 keyword인지 확인 후 아니면 다시 넣고 다음 원소 꺼내는 그런 용도로 사용하기 어렵다.

당연히, 이는 FIFO가 아니기 때문!

어떻게든 pq로 해결하겠다면 원소를 다 꺼내야 되는데
어차피 pq 말고도 목적에 맞는 자료구조가 따로 존재하기 때문에 굳이 그럴 필요가 없다.


⭐⭐⭐ LinkedHashMap을 통한 LRU 구현​

LinkedHashMap의 accessOrder를 사용하면 LRU 구현이 아주 쉬워진다.

⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐

accessOrder는 기본 false로, 이 경우 insertOrder로 작동한다.

  • insertOrder는 삽입된 순서를 보장하고 (FIFO)
  • accessOrder는 삽입/수정/조회 순서를 보장한다. (LRU)

따라서 accessOrder를 true로 설정하고 put() 또는 get()하면 자동으로 LRU로 작동하는 것이다.

다만 accessOrder가 생성자의 3번째 인자라서, 생성시 인자를 다 적어줘야 한다.

생성자 스펙은 Java SE 8 API docs에서 확인할 수 있다.


Map<String, Boolean> cache = new LinkedHashMap<>(cacheSize+1, 1.0f, true);

결과적으로 상단과 같이 생성하였는데, 약간 머리를 굴려서 resize가 일어나지 않도록 의도했다.

  • 초기 사이즈를 cacheSize + 1로 설정
  • loadFactor를 100%로 설정

구현할 LRU 로직 상 LinkedHashMap의 size는 cacheSize를 넘지 않으므로, resize가 발생하지 않는다.

if (cache.size() >= cacheSize) { // cache is full -> swap
    // NoSuchElementException 조심
    // corner case 처리 안하면 NSEE 발생
    cache.remove(cache.keySet().iterator().next());
}

그리고 swap이 필요할때 keySet().iterator().next()를 통해 head를 찾아서 제거한다.

head나 tail 접근법은 스택오버플로를 참고했다.


⭐ 추가 레퍼런스​

자바의 HashMap과 C++의 map을 비교하다가 내부 구현을 좀 찾아봤는데 값진 내용들이 많았다.

Internal Working of HashMap in Java​

자바의 HashMap은 Array 형태의 버킷과 각 인덱스에 연결된 LinkedList로 구성된다.

이는 해시 충돌을 handling하기 위함으로, 자바는 해시 충돌 전략 중 체이닝을 채택했다.

참고로 자바의 LinkedList 구현은 Doubly Linked List이다.


자바 HashMap의 하이브리드 구현​

출처: https://yongtapark95.tistory.com/77

스택오버플로에 의거하면 자바의 HashMap은 TREEIFY_THRESHOLD 상수를 기반으로 충돌 횟수가 임계치 도달 시 do-while을 돌며 내부 구현을 LinkedList에서 RBT로 변환한다.

이 때 Node -> TreeNode 로의 노드 변환 오버헤드가 있으며 JEP 180을 참조하면, 해당 오버헤드는 메모리 효율 trade-off 측면에서 감수한 것임을 알 수 있다.

자바가 언제부터 효율성 신경썼다ㄱ.. (검열삭제)

C++은 내부 구현이 디폴트 RBT이며 key 기준 오름차순 정렬 보장임을 생각할때, 자바와의 차이점이 꽤나 흥미롭다.


그래서 사실 O(1) guarantee access가 아님​

일반적으로 해시맵은 access가 O(1)O(1)이라고 알려지나 이는 해시 충돌이 발생하지 않은 경우이다.

엄밀히 따지면 최악의 상황은 O(n)O(n) 또는 O(log n)O(log\,n)이다.

자바 기준, 해시 충돌이 7번까지 발생하면 LinkedList worst access의 O(n)O(n)을 따르게 되고

8번 충돌부터 RBT로 변환되어 BST worst access의 O(log n)O(log\,n)을 따르게 된다.

하지만 엄밀히 따졌을 때 그렇다는거지, 웬만하면 O(1)이기 때문에 크게 걱정할 필요는 없다.


📚 더 읽어볼거리​


메모​

  • 복습하면 좋을 문제 수준이 아니라 복습 안하면 큰일나는 문제이다.
  • head 반환 메소드 없어서 entrySet().iterator().next()로 접근해야한다니.. ㅜㅜ