(2018카카오) 캐시 LRU(Least Recently Used) 알고리즘 Java

위 문제는 LRU(Least Recently Used)알고리즘을 이용한 방법이다.

대표적인 LRU 알고리즘의 문제로 꼽힌다.

 

LRU 알고리즘 설명

사진출처: gomguard.tistory.com/115

페이지 교체 알고리즘 - LRU

 

해쉬맵을 이용한 코드다.

 

코드는 길지만, 실행속도는 빠른편이다.

 

여기서도 toLowerCase()로 소문자로 모두 변환해주었다.

 

각 상황을 if문에 따라 나누었는데, cacheSize=0인경우를 고려하지않았었는데,

개인적으로 문제를 꼼꼼히 읽어야겠다는 생각을 했다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        Map<String, Integer> map = new HashMap<>();

        int i = 0;
        for (String str : cities) {
            str=str.toLowerCase();
            if(cacheSize==0){
                i+=5;
                continue;
            }


            if (map.size() < cacheSize) {//초기에 캐시 꽉찰때까지 값 추가
                if (map.getOrDefault(str, 1) != 1){
                    map.put(str, i);
                    i++;
                    continue;
                }
                map.put(str, i);
                i += 5;
            } else {
                //기존에 없던 key인경우
                if (map.getOrDefault(str, 1) == 1) {
                    int min = -1;//가장오래된타임
                    String minKey = "";
                    for (Map.Entry<String, Integer> entry : map.entrySet()) {
                        if (min == -1) {//초기값.
                            min = entry.getValue();
                            minKey = entry.getKey();
                        } else {//비교연산. value비교로 가장오래된 key찾기
                            if (min != Math.min(min, entry.getValue())) {
                                min = entry.getValue();
                                minKey = entry.getKey();
                            }
                        }
                    }
                    map.remove(minKey);
                    map.put(str, i);
                    i += 5;
                } else {//기존에 있는 key의경우 업데이트
                    map.put(str, i);
                    i++;
                }
            }
        }

        return i;
    }
}

 

다른 사람의 코드이다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
  public int solution(int cacheSize, String[] cities) {
        int time = 0;

        if (cacheSize == 0) {
            return cities.length * 5;
        }

        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < cities.length; i++) {
            boolean hit = ((LinkedList<String>) queue).removeFirstOccurrence(cities[i].toUpperCase());
            queue.add(cities[i].toUpperCase()); 
            time += 1;
            if (!hit) {
                time += 4;
                if (queue.size() > cacheSize) {
                    String removed = ((LinkedList<String>) queue).removeFirst();
                }
            }
        }

        int answer = time;
        return answer;
    }
}

removeFirstOccurence()메소드에 대해 알아봐야겠다.

 

위에서 removeFirstOccurence는 실행속도측면에서 오래된것부터 탐색하기때문에 많은 향상을 시킨다.

 

[ removeFirstOccurrence() / removeLastOccurrence() ]

• 첫 번째(head) / 마지막(tail) 부터 검색해서 삭제

큐를 LinkedList로 형변환하여 removeFirstOccurence 할 객체가 있으면 hit이 true일것이다.

아닌경우 false를 반환하므로 cache miss => +5를해야 한다(위에서는 1+4로 연산해줌).

 

추가적으로,,

 

[ removeFirst() / removeLast() ]

• 첫번 째 값(head), 마지막 값(tail) 삭제
• removeFirst()는 remove(0)과 같음