[Programmers/2018 KAKAO BLIND RECRUITMENT] 캐시 - Java

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 캐시

 

 

 

문제 링크

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

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

 

 

문제 풀이

 

cache에 있는 도시이거나 cache사이즈가 초과하면 가장 오래된 도시를 지운다.

cache.add() 로 새로운 도시 갱신해준다. 

 

 

 

 

 올해 초 정처기 자격증 공부를 했을 때 LRU알고리즘이란걸 알게됐다. 단순히 글로 보기만 했었는데 이렇게 문제로 접하게 돼서 신기했다. 처음 이 문제를 봤을 땐 LRU알고리즘 원리를 까먹었어서 대체 무슨 규칙인가 하고 예시를 한참 들여다 보다 겨우 생각해냈다. 어떻게 풀까 생각을 많이 했다. hashmap, 배열, list 등등을 생각해보다 list가 가장 조작하기 쉬울 것 같아서 코드 작성을 시작했다.

cache list에 있건 없건 갱신은 해야하므로 도시 갱신은 밖으로 빼두었다. 그래서 이미 있는 도시라면 삭제하고 +1 을 해주고 없다면 +5 만 하는 방법으로 풀었고, 도시 갱신후 그 사이즈가 cacheSize를 넘어간다면 가장 오래된 도시를 삭제하는 구조로 만들었다.

public static int solution(int cacheSize, String[] cities) {	
	int answer = 0;
	int size = cities.length;
	LinkedList<String> cache = new LinkedList<>();
	String city = "";
		
	for(int i = 0; i < size; i++) {
		city = cities[i].toUpperCase();
			
		if(cache.contains(city)) { //cache hit
			cache.remove(city);
			answer++;
		}else { //cache miss
			answer += 5;
		}
		cache.add(city);
		
		if(cache.size() > cacheSize) {
			cache.removeFirst();
		}
	}
	return answer;
}