뜨균이의 개발 생활

링크

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

문제

풀이

• 캐시 교체 알고리즘은 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 를 사용했고 어려운 기술은 없었다.