성능 요약
-
메모리: 78.5 MB, 시간: 2.76 ms - Answer Code1(23.01.31)
-
메모리: 81.4 MB, 시간: 2.66 ms - Answer Code2(23.02.20)
구분
코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT
Answer Code1(23.01.31)
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
ArrayList<String> cache = new ArrayList<>();
if(cacheSize == 0) // 캐시크기가 0
return cities.length * 5;
for(int i=0; i<cities.length; i++) {
cities[i] = cities[i].toUpperCase(); // 대소문자 구분X
if(cache.contains(cities[i])) { // cache hit
cache.remove(cities[i]);
cache.add(cities[i]);
answer += 1;
}
else { // cache miss
if(cache.size()==cacheSize) {
cache.remove(0);
cache.add(cities[i]);
}
else
cache.add(cities[i]);
answer += 5;
}
}
return answer;
}
}
Answer Code2(23.02.20)
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
List<String> cacheList = new ArrayList<>();
if(cacheSize == 0) {
return cities.length * 5;
}
for(int i = 0; i < cities.length; i++) {
cities[i] = cities[i].toLowerCase(); // 소문자로 변환
//cache hit
if(cacheList.contains(cities[i])) {
cacheList.remove(cities[i]);
cacheList.add(cities[i]);
answer += 1;
}
//cache miss
else {
answer += 5;
if(cacheList.size() == cacheSize) {
cacheList.remove(0);
cacheList.add(cities[i]);
}
else {
cacheList.add(cities[i]);
}
}
}
return answer;
}
}
Review
-
LRU(Least Recently Used)에 대해 알고 있어야 풀 수 있는 문제였다.
-
LRU: 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다. -
LRU 알고리즘 구현을 보통 자료구조
Queue(큐)로 사용하면 편리하지만, Java에서는LikedList가Queue의 구현체이므로Likedlist로 구현했다.
-
-
cache hit 인 경우(캐시에 존재한 경우) hit된 데이터를 기존 위치에서 가장 최근 위치로 이동 시킨다.(기존 위치를 제거하고 맨 뒤에 데이터를 추가한다)
-
cache miss 인 경우
-
새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일한다면, 꽉차있는 의미이므로 가장 오랫동안 사용하지 않은 것을 제거하고, 맨 뒤에 데이터를 추가한다.
-
새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일하지 않다면, 맨 뒤에 데이터를 추가한다.
-