구르는 돌에는 이끼가 끼지 않는다

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

위 문제는 어떻게 보면 불친절한 문제입니다. 문제를 푸는 사람 입장에서 문제에서 말하는 [

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.

]라는 전제 조거은 말근데로 캐기 교체 알고리즘을 풀지 않으면 풀수 없는 문제 입니다. 

예전에도 카카오 코테를 참여했을때도 다음 문제를 못풀었던 기억이 있네요. 

어쨋든 캐시 교체 알고리즘은 다음과 같습니다. 

캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.

이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다.

라고 설명하고 있습니다. 

즉, 데이터의 접근을 빠르게 하기 위해서 나온 캐시 알고리즘이라고 생각하면 됩니다. 

캐시의 hits의 경우에는 캐시안에 데이터가 존재하므로 time값이 +1이 증가하고 

캐시 miss의 경우에는 캐시안에 데이터가 존재하지 않으므로 time값이 +5가 증가하게 됩니다. 

저는 다음과 같이 풀었습니다.

package com.ji.test;

import static org.junit.Assert.assertEquals;

import org.junit.jupiter.api.Test;

import com.ji.study.Cache;

public class CacheTest {
	
	@Test
	void test() {
		
		Cache test = new Cache();
		
		assertEquals(50, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(21, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
		assertEquals(60, test.solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(52, test.solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
		assertEquals(25, test.solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
		assertEquals(16, test.solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
		
	}

}

package com.ji.study;

import java.util.LinkedList;
import java.util.Queue;

public class Cache {
	
	public static int solution(int cacheSize, String[] cities) {
		int excuteTime = 0;
		Queue cacheQueue = new LinkedList<String>();

		if (cacheSize == 0) {
			excuteTime = cities.length * 5;
		} else {

			for (String city : cities) {
				city = city.toLowerCase();

				if (cacheQueue.contains(city)) {
					cacheQueue.remove(city);
					excuteTime++;
				} else {
					if (cacheQueue.size() >= cacheSize)
						cacheQueue.poll();
					
					excuteTime = excuteTime + 5;
				}
				
				cacheQueue.offer(city);
				
			}

		}

		return excuteTime;
	}

}