[프로그래머스/java] 2018 카카오 블라인드 1차 캐시 & LRU 알고리즘

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

풀면서 재밌었던 문제이다.

 

LRU (Least Recently Used) 알고리즘

Least Recently Used (LRU) is a common caching strategy. It defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.

• OS의 페이지 교체 알고리즘 중 하나.
• 문제에 언급된 LRU 알고리즘은 보편적인 캐싱 전략이며, 캐시가 다 찼을 때 새로운 값을 넣기 위해 가장 오랫동안 사용되지 않은 것을 버리는 방식이다.
• cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우.
• cache miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우.

 

아래 이미지를 통해 LRU알고리즘의 동작방식을 살펴보겠다.  0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 가 주어지고, cache size는 3이다. 빨간색 부분이 교체되는 가장 오랫동안 참조되지 않은 페이지이고, 노란 부분이 제일 최근에 참조된 페이지이다. 

출처 : https://www.educative.io/answers/what-is-the-least-recently-used-page-replacement-algorithm

• java에서 Doubly Linked List를 이용해서 구현할 수 있다.
  • 사용이유 : list의 front(head)나 end(tail)에 접근시에 모두 O(1) 상수시간 내에 접근 가능하기 때문이다. 그리고 insert, delete시에도 상수시간이다.

 

---

풀이

처음엔 '가장 오랫동안 참조되지 않은 페이지'를 찾으려면 어떻게 해야하지? 싶어서 LinkedHashMap을 이용해서 value에 참조된 횟수를 저장하는 식으로 풀려고 했다. 그런데 최근 참조된 페이지를 head에 두고, 오랫동안 참조되지 않은 페이지를 tail에 두는 식으로 풀면 굳이 몇번 참조되었는지의 상세한 정보는 필요가 없어서 LinkedHashSet을 이용해서 푸는 풀이로 바꿨다.

 

LinkedHashSet을 이용하면 값의 중복은 비허용하고, 삽입한 순서를 기억하기 때문에 아래 방식으로 풀었다.

1. hit한 경우에는 element를 remove했다가 다시 insert해준다. => 최신값으로 유지. 
2. 가장 오랫동안 참조되지 않은 element는 맨 앞에 남게 된다.

전체코드

import java.util.*;
 
 
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        final int HIT = 1;
        final int PASS = 5;
 
        Set<String> hashSet = new LinkedHashSet<String>(cacheSize);
 
        for (String city : cities) {
            // 대소문자 구분 안하므로
            String c = city.toLowerCase();
 
            if (hashSet.isEmpty()) {
                hashSet.add(c);
                answer += PASS;
            } else {
                // 가장 오래 참조되지 않은 값을 제거
                if (cacheSize < hashSet.size()) {
                    hashSet.remove(hashSet.stream().findFirst().get());
                }
                //hit (hit하면 맨 뒤로 보내줘서 최신으로 만든다)
                if (hashSet.contains(c)) {
                    hashSet.remove(c);
                    hashSet.add(c);
                    answer += HIT;
                }
                //pass
                else {
                    hashSet.add(c);
                    answer += PASS;
                }
            }
        }
        return answer;
    }
}

 

 

 

 

 

---

 

참고자료

https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

LRU Cache 이해하기