[2018 Kakao Blind Recruitment] 캐시 Java 풀이
Problem
https://programmers.co.kr/learn/courses/30/lessons/17680
LRU Cache
LRU(Least Recently Used) 방식은 말 그대로 가장 옛날에 사용된 것을 버리는 방식이다. 즉 캐시에서 오랫동안 참조되지 않은 데이터를 교체하겠다는 말이다.
Solution
LRU Cache를 구현하는 문제이다.
2가지 방법으로 구현했는데, 첫 번째 방법은 최근에 공부하고 있어서 Java 8을 적극적으로 활용해보려 했고, 두 번째 방법은 자료구조를 활용하려 했다.
방법 1
각 데이터를 저장하는데, 데이터에 시간을 매겨서 지워야 하는 상황이 생기면 시간이 가장 큰 데이터를 삭제한다.
만약 캐시에 존재하는 데이터를 참조하면, 시간을 초기화 시켜준다.
데이터에 대해서 시간을 맵핑하는 HashMap을 만들어서 LRU 캐시를 구현한다.
방법 2
- FIFO(First In First Out) 방식과 유사하다는 느낌을 받았다. 먼저 들어갔던 녀석이 참조되지 않았다면 먼저 나갈 것이다.
- 그렇다면 FIFO 방식으로 삽입하되 만약 어떤 요소가 참조되면 그 요소는 다시 맨 앞으로 보내버린다.
만약에 사이즈가 3인 캐시에 [2, 3, 1, 4, 3]이 순서대로 저장되면, 아래와 같은 순서대로 캐시에 데이터가 저장된다.
4 번째 순서에 4가 들어오자 가장 오랫동안 참조되지 않았던 2가 빠지게 된다.
5 번째 순서에 3이 들어오자 기존에 있던 3이 맨 앞으로 옮겨졌다.
삽입할 때에는 맨 앞에 삽입하고, 제거할 때는 맨 뒤를 제거하기 위해 이중 연결 리스트를 만들기로 했다. 이는 중간 요소를 제거하고 이어 붙이는 데에도 용이하다.
SOURCE CODE (JAVA)
방법 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
public class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
HashMap<String, Integer> map = new HashMap<>();
for (String cityOrigin : cities) {
String city = cityOrigin.toLowerCase(); // city의 대소문자를 무시한다.
if (map.containsKey(city)) { // Cache Hit
map.put(city, 0); // 시간 초기화
answer += 1;
} else { // Cache Miss
map.put(city, 0); // 데이터 추가
answer += 5;
if (map.size() > cacheSize) { // 사이즈 오버
// map에서 value가 가장 큰 요소의 key
String maxKey = map.entrySet().stream()
.max(Comparator.comparingInt(Map.Entry::getValue))
.get().getKey();
map.remove(maxKey); // 시간(value)이 가장 큰 요소 삭제
}
}
// map의 각 요소마다 시간(value) 증가
for (Map.Entry<String, Integer> next : map.entrySet()) {
next.setValue(next.getValue() + 1);
}
}
return answer;
}
}
map에서 value가 가장 큰 요소를 찾을 때 Stream API를 활용하였다.
20 ~ 22번 라인은, map의 entrySet을 stream으로 만들어서 순회하며 value가 최대인 Entry를 찾아 key를 구한다.
방법 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.util.*;
public class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
LRUCache lruCache = new LRUCache(cacheSize);
for(String city : cities) {
answer += lruCache.add(city.toLowerCase());
lruCache.print();
}
return answer;
}
static class LRUCache {
int size;
int count;
HashMap<String, Node> map;
DoubleLinkedList linkedList;
LRUCache(int size) {
this.size = size;
count = 0;
map = new HashMap<>();
linkedList = new DoubleLinkedList();
}
int add(String data) {
if (size == 0) // Cache의 크기가 0이라면 저장할 수 없다.
return 5;
if (map.containsKey(data)) { // Cache Hit
Node node = map.get(data);
linkedList.update(node); // Node 위치를 업데이트한다.(맨 앞으로 보낸다)
return 1;
} else { // Cache Miss
if (size <= count) // 캐시에 공간이 없다면
deleteTail(); // tail을 지운다.
Node node = new Node(data); // 새로운 Node
linkedList.add(node); // Node를 head에 추가한다.
map.put(node.key, node);
count++;
return 5;
}
}
void deleteTail() {
Node tailNode = linkedList.delete();
map.remove(tailNode.key);
count--;
}
void print() {
Node node = linkedList.head;
while (node != null) {
System.out.print(node.key + " ");
node = node.next;
}
System.out.println();
map.keySet().stream().map(key -> key + " ").forEach(System.out::print);
System.out.println();
System.out.println();
}
}
static class DoubleLinkedList {
Node head;
Node tail;
// 맨 앞에 추가한다 = node는 head가 된다
void add(Node node) {
// head답게 prev와 next를 설정한다.
node.prev = null;
node.next = head;
if (head != null) // head가 있으면 (리스트 길이가 1 이상)
head.prev = node; // head를 node와 연결
head = node;
if (tail == null) // tail이 없으면 (빈 리스트)
tail = node; // node가 head이면서 tail
}
// 맨 뒤를 삭제한다
Node delete() {
Node tailNode = tail;
tail = tailNode.prev; // 이전 노드가 tail이 된다.
if (tail == null) // tail이 없으면 (리스트 길이가 1이면)
head = null; // head가 null이다.
else // tail이 있으면 (리스트 길이가 2 이상, 빈 리스트에서 delete()를 호출하는 경우는 제외)
tail.next = null; // tail의 next는 null
return tailNode;
}
// node를 맨 앞으로 보낸다 = node의 앞뒤를 연결해준 후 맨 앞에 추가(add)한다.
void update(Node node) {
Node prevNode = node.prev;
Node nextNode = node.next;
if (prevNode != null) // 이전 노드가 있으면
prevNode.next = nextNode; // 이전 노드와 다음 노드를 연결
else // 이전 노드가 없으면 (node == head)
return; // 이미 head이므로 더이상 로직이 필요없다.
if (nextNode != null) // 다음 노드가 있으면
nextNode.prev = prevNode; // 다음 노드와 이전 노드를 연결
else // 다음 노드가 없으면 (node == tail)
tail = prevNode; // 이전 노드가 tail이 된다.
// tail.next = null
// 위에서 이전 노드를 확인하면서 이전 노드에는 이미 다음 노드(null)가 연결되어있다.
add(node);
}
}
static class Node {
String key;
Node next;
Node prev;
Node(String key) {
this.key = key;
}
}
}
최대한 간결하게 리팩토링 한다고 했지만 자료구조를 사용하여 직접 구현하다보니 코드가 많이 길어졌다.
하다가 많이 헤맸는데, 주요한 이유는 이중 연결 리스트에서 head와 tail 때문이었다. head을 설정할 때 head.prev를 null로, tail을 설정할 때 tail.next를 null로 바꾸어주어야 한다. 이 부분을 세밀하게 신경쓰지 않으면 무한루프를 돌거나 NullPointerException이 발생한다.
OFF THE RECORD
방법 1은 방법 2에 비해서 긴 시간이 걸린다. 특정 테스트 케이스에서 방법 1은 323.17ms이 걸렸다면, 방법 2는 59.98ms가 걸렸다. 해당 테케 뿐 아니라 전체적으로 5배 정도 차이났다.
방법 1은 매번 HashMap에서 시간(value)이 최대인 값을 찾아야하니 더 오래 걸릴 수 밖에 없다고 생각한다.
댓글 남기기