[프로그래머스/자바] 캐시 풀이 - 2018 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2018 KAKAO BLIND RECRUITMENT 1차 Level 2 문제다.

 

 

LRU의 지식만 있다면 어렵지 않게 풀 수 있다.

처음엔 우선순위 큐로 풀었는데, 값이 있는지 검사하기 위해 큐의 값을 하나하나씩 탐색하는 과정에서 시간 초과가 발생한 것 같다. 

LRU를 구글링 해보니 LinkedHashMap으로 자주 구현하는 것 같아 이걸로 구현했다.

ArrayList도 인덱스가 아닌 값으로 remove가 가능하기 때문에 ArrayList로 구현해도 될 것 같다.

 

 

 

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

먼저 LinkedHashMap을 생성해주는데, 생성시 매개변수 3개를 넣어준다.

 

1) 가장 처음에 넣은 initialCapacity는 bucket 사이즈를 말한다.

이번 문제에서는 cacheSize만큼의 데이터만 들어갈 것이기 때문에 cacheSize로 설정해준다.

 

2) 두 번째 loadFactors는 데이터들이 bucket에 다시 분배되는 rehashing을 위한 값이다.

일반적으로 최적은 0.75f라고 한다.

 

3) 마지막 accessOrder는 이번 문제에서 가장 중요한, 값을 정렬할 기준이다.

accessOrder가 false라면 삽입되는 순서대로 정렬하는 것(insertion-order)이고 true라면 접근된 데이터 별로 정렬하는 것(access-order)이다.

예를 들어 1 2 3 순서대로 키가 삽입되어 정렬이 되어있고, map.get(3)을 했다면 3이 접근된 것이므로 3 1 2 순서대로 정렬이 되는 것이다.

이번 문제에서는 LRU, 즉 가장 오랫동안 접근되지 않은 데이터가 가장 먼저 삭제되어야 하므로 access-order를 사용한다.

 

 

그리고 removeEldestEntry를 Override해준다. 

return을 size() > cahceSize로 두었다.

즉, map의 size가 cacheSize 넘었다면 가장 오랫동안 접근되지 않은 데이터를 삭제해 항상 map의 사이즈를 cacheSize 이하로 유지하는 것이다.

 

이렇게 map을 생성해주면 간단하게 LRU 캐시를 구현한 것이다.

cities의 배열을 하나씩 탐색하면서 해당 도시가 map에 존재하지 않는다면 ans에 5를 더해주고 존재한다면 1을 더해준다.

이때 containsKey를 해주는 것도 접근이라고 판단하고 자동으로 access-order 정렬이 된다.

그리고 도시를 map에 넣어준다. removeEldestEntry를 구현해주었기 때문에 캐시가 가득 차있어도 가장 오래된 map이 삭제될 것이다.

 

 

 

배운점 및 느낀점

LinkedHashMap은 삽입 순서대로 정렬이 필요할 때만 사용했었는데,

removeEldestEntry와 생성자의 매개변수를 통해 access-order로도 정렬할 수 있다는 것을 알았다.

처음엔 removeEldestEntry만 구현하고 생성자에는 아무 값을 주지 않아 11, 15, 18, 19, 20 테케를 틀렸었다.

생성자의 세번째 매개변수를 true로 주어 언제 접근했는지를 기준으로 정렬하는 것이 중요하다!

 

 

 

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
		LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(cacheSize, 0.75f, true) {
			@Override
			protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
				return size() > cacheSize;
			}
		};
		
		int ans = 0;

		for(String s : cities) {
			String city = s.toLowerCase();
			ans += map.containsKey(city) ? 1 : 5;
			map.put(city, 0);
		}
		
		return ans;
    }
}