링크
https://programmers.co.kr/learn/courses/30/lessons/17680
코딩테스트 연습 - [1차] 캐시
3 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 50 3 ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] 21 2 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Ro
programmers.co.kr
문제
풀이
- 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
- cache hit일 경우 실행시간은 1이다.
- cache miss일 경우 실행시간은 5이다.
1. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
LRU 알고리즘은 사용된 데이터의 경우 제거 후 순위로 변경해준다.
A, B, C, D 라는 문자가 차례대로 들어온 후
캐시에서 제거될 때 A, B, C, D 순서로 제거된다.
E 문자열 삽입
A는 제거되고 그 뒤에 있던 B가 다음 제거 타겟이다.
여기에서 중간에 있는 C를 요청받으면
이미 C가 존재하기 때문에 제거되는 데이터는 없다.
하지만 순서가 바뀐다.
B 다음으로 C가 제거 타겟이였지만
C가 새로 들어온 신입처럼 후순위로 배치된다.
이것이 LRU 알고리즘이다.
2. cache hit일 경우 실행시간은 1이다.
데이터가 들어왔을 때 캐시에 존재하는 데이터면 +1
3. cache miss일 경우 실행시간은 5이다.
데이터가 들어왔을 때 캐시에 없는 데이터면 +5
캐시 사이즈 : 3
*대소문자를 구분하지 않기 때문에 일괄적으로 대문자로 변환하여 비교하였습니다.
데이터 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
JEJU 는 캐시에 없는 데이터
캐시 [JEJU]
수행 시간(0) : +5
데이터 ["Pangyo", "Seoul", "NewYork", "LA"]
PANGYO 는 캐시에 없는 데이터
캐시 [JEJU, PANGYO]
수행 시간(5) : +5
데이터 ["Seoul", "NewYork", "LA"]
SEOUL 은 캐시에 없는 데이터
캐시 [JEJU, PANGYO, SEOUL]
수행 시간(10) : +5
데이터 ["NewYork", "LA"]
NEWYORK 은 캐시에 없는 데이터
캐시 사이즈에 자리가 없기 때문에 제일 먼저 들어온 데이터 제거 후 삽입
[JEJU, PANGYO, SEOUL]
[PANGYO, SEOUL]
[PANGYO, SEOUL, NEWYORK]
수행 시간(15) : +5
데이터 ["LA"]
LA 는 캐시에 없는 데이터
캐시 사이즈에 자리가 없기 때문에 제일 먼저 들어온 데이터 제거 후 삽입
[PANGYO, SEOUL, NEWYORK]
[SEOUL, NEWYORK]
[SEOUL, NEWYORK, LA]
수행 시간(20) : +5
총 수행 시간 : 25초
위의 로직 구현
import java.util.LinkedList;
import java.util.Queue;
class Solution {
/**
* 카카오 캐시
* @param cacheSize
* @param cities
* @return
*/
public int solution(int cacheSize, String[] cities) {
int answer = 0;
int count = cities.length;
Queue<String> qu = new LinkedList<>();
for (int i = 0; i < count; ++i) {
String str = cities[i].toLowerCase();
// 캐시 사이즈가 0일 경우 밑의 로직 수행 X -> 수행 시간 +5
if (0 == cacheSize) {
answer += 5;
continue;
}
// 캐시에 존재하는 데이터면 순서 변경 후 수행 시간 +1
if (qu.contains(str)) {
qu.remove(str);
qu.add(str);
++answer;
continue;
}
// 캐시 사이즈에 자리가 없을 경우 먼저 들어온 데이터 제거 후 삽입 수행 시간 +5
if (qu.size() >= cacheSize) {
qu.poll();
qu.add(str);
answer += 5;
continue;
}
// 그 외 캐시에 삽입 후 수행 시간 +5
qu.add(str);
answer += 5;
}
return answer;
}
}
후기
* 난이도 (5점 만점)
5 : 풀 줄 알면 기업 코딩테스트는 문제 없음.
4 : 평균적인 기업 코딩테스트의 중간 이상.
3 : 평균적인 기업 코딩테스트의 쉬운 문제 .
2 : 알고리즘 문제를 연습하고 있다면 풀 수 있는 문제.
1 : 시간이 오래 걸리지 않고, 누구나 풀 수 있는 문제.
난이도는 생각보다 쉬운 편이었으며 LRU 알고리즘을 이해한다면 충분히 풀 수 있다.
LRU 알고리즘을 풀기 위해 자료구조 Queue 를 사용했고 어려운 기술은 없었다.
'카카오코딩테스트 풀이 > 2018' 카테고리의 다른 글
| [카카오 코딩 테스트 2018 신입 공채] 다트 게임- JAVA 자바 (0) | 2021.08.13 |
|---|---|
| [카카오 코딩 테스트 2018 신입 공채] 비밀지도 - JAVA 자바 (0) | 2021.08.13 |
