[알고리즘] 캐시 (2018 카카오)

코딩테스트 연습 - [1차] 캐시

 예전에 카카오 연습문제를 찾아보다가 한 번 풀었봤던 기억이 있는데 그 당시엔 프로그래머스를 몰라서 프로그래머스에서 푼게 아니라 그냥 이클립스에다가 돌리고 나와있는 테스트 케이스만 돌려봤었다.

 난이도 자체는 쉬운 문제이다. 전형적인 컴퓨터 과학의 개념을 시뮬레이션하는 문제로써, 캐시를 구현해보는 것인데 캐시를 무엇으로 구현하느냐가 관건이다.

 

Solution

 캐시 구현은 뭘 해도 상관은 없다. List든 ArrayList든 Queue든.... 보통 제일 정석적으로 생각한 게 Queue일 것 같은데 캐시의 교체 알고리즘이 LRU (Least Recently Used) 인지라 나는 PriorityQueue를 사용했다.

 

 LRU는 말그대로 가장 오랫동안 사용되지 않은 요소부터 제거한다는 뜻이다. '서울', '대구', '부산' 과 같은 순서로 캐시에 들어갔을 때, 순서상 '서울'이 가장 오래전에 사용되었기에 제거대상 1순위가 된다.

 때문에 City라는 클래스를 만들어서 도시 이름, index 값을 속성으로 두고 index 값이 작을수록 가장 오래전에 사용된 것이기에 Queue에 앞쪽에 두게 정렬을 했다.

 

 만약 캐시 내에 cities[i]가 이미 있다면 cache hit, 없으면 cache miss가 된다. cache hit일 때는 cache안에 있는 cities[i]를 지우고 새로 index값을 갱신하여 new City(cities[i], i)를 캐시에 넣어준다.

 cache miss일 땐 cache가 꽉 차있다면 poll()해서 가장 오래전에 사용된 도시를 지우고 현재 도시를 넣어준다.

 

import java.util.*;

class Solution {


	public int solution(int cacheSize, String[] cities) {
		int answer = 0;

		//캐시가 0이면 무조건 cache miss
		if(cacheSize == 0)
			return cities.length * 5;
		
		//index (언제 사용됐는지 지표) 값이 낮을 수록 사용된지 오래됨
		PriorityQueue<City> cache = new PriorityQueue<City>((o1, o2)-> o1.index - o2.index);

		for(int i = 0;i < cities.length;i++)
		{
			City city = new City(cities[i].toLowerCase(), i);

			if(cache.isEmpty())
			{
				cache.offer(city);
				answer += 5;
			}
			else
			{
				//캐시 hit
				if(cache.contains(city))
				{
					cache.remove(city);
					cache.offer(city);
					answer++;
				}
				//캐시 miss
				else
				{
					//캐시가 꽉찼다면 가장 오래전에 사용된 city 비움
					if(cache.size() == cacheSize)
						cache.poll();
					cache.offer(city);
					answer += 5;
				}
			}
		}
		return answer;
	}

	class City{

		String name;
		int index;

		public City(String name, int index)
		{
			this.name = name;
			this.index = index;
		}

		@Override
		public boolean equals(Object obj) {
			City city = (City) obj;
			return name.equals(city.name);
		}
	}
}