[카카오 블라인드 2018] [1차] 캐시 - java

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

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

class Solution {
	int curCacheSize = 0;
    public int solution(int cacheSize, String[] cities) {
    	int answer = 0;
    	CacheCity[] cache = new CacheCity[cacheSize];
    	if(cacheSize == 0) {
    		return cities.length*5;
    	}
    	
    	
    	for(int i=0; i<cities.length; i++) {
    		answer += checkCache(i, cities[i].toLowerCase(), cache, cacheSize);
    		timeRefreshCache(i, cache);
    		
    	}
    	return answer;
    }
    
    
    private int checkCache(int idx, String cityName, CacheCity[] cache, int cacheSize) {
		for(int j=0; j<curCacheSize; j++) {
			if(cache[j].cityName.equals(cityName)) {
				cache[j].time = 0;
				return 1;
			}
		}
		updateCache(cache, cityName);
		return 5;
	}
    
	void updateCache(CacheCity[] cache, String cityName){
    	int idx = 0;
    	int maxTime = 0;
    	for(int i=0; i<cache.length; i++) {
    		if(cache[i] == null) {
    			cache[i] = new CacheCity(cityName);
    			curCacheSize++;
    			return;
    		}
    		
    		if(cache[i].time > maxTime) {
    			maxTime = cache[i].time;
    			idx = i;
    		}
    	}
    	cache[idx].cityName = cityName;
    	cache[idx].time = 0;
    }
    
    void timeRefreshCache(int idx, CacheCity[] cache) {
    	for(int i=0; i<curCacheSize; i++) {
    		cache[i].time++;
    	}
    }
    
    class CacheCity{
    	String cityName;
    	int time;
		public CacheCity(String cityName) {
			this.cityName = cityName;
			this.time = 0;
		}
    }
}

이 문제의 조건인 LRU는 가장 오랫동안 사용되지 않은 항목을 내보내는 알고리즘입니다.

 

CacheCity라는 클래스에서 도시 이름과 사용되지 않은 시간을 저장할 time을 정의했습니다.

checkCity()에서는 cache에 도시 이름이 있는지 체크하고, 있다면 answer += 1과 cache의 time을 0으로 초기화해줍니다.

없다면 answer+=5를 하고 캐쉬의 상태를 업데이트 합니다.

updateCache()에서는 캐쉬에 차있지 않다면 생성자로 만들고, 캐쉬가 가득 차있으면 가장 오래 사용하지 않은 인덱스에 값을 갱신합니다.

timeRefreshCache()는 캐쉬의 time값들을 전부 1씩 올려줍니다.

 

조금 번거롭게 코드를 짰는데... List를 이용해서 큐와 비슷한 형식으로 맨 앞에 있는 값이 가장 오랫동안 사용되지 않은 항목으로 remove해주고, 캐시에 저장할 항목을 add 해주는 방식으로 짜면 코드가 훨씬 간결해집니다.