캐시

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

코딩테스트 연습 - [1차] 캐시 | 프로그래머스

---

처음에 문제를 여러번 읽었는데, 이해하기가 어려운 문제였습니다. 캐시의 크기가 주어지면, 도시의 이름을 처음부터 순서대로 캐시에 넣으면서, 캐시 안에 도시의 이름이 없으면 실행시간을 5초 더하고, 캐시 안에 도시 이름이 있으면 실행시간을 1초 더해서 최종적으로 cities 배열을 처음부터 끝까지 돌았을 때의 실행시간을 구하는 문제였습니다. 조건에 캐시 교체 알고리즘은 LRU(Least Recently Used)을 사용한다고 했는데, 어디서 들어보긴 했는데, 무엇인지 기억이 안났습니다......... 그래서 찾아보니 LRU 는 가장 오랫동안 사용하지 않은 페이지를 제거하는 알고리즘인데, 운영체제 시간에 배웠던 것으로 기억했습니다. 카카오 문제들의 특징은 삼성과 다르게 이러한 알고리즘도 알고 있어야 풀 수 있구나 생각을 해봤고, 기초적인 알고리즘은 숙지하고 있어야 되겠다고 생각했습니다.

캐시에 들어있는 도시중에 가장 오랫동안 사용하지 않은 도시이름을 빼야겠구나 생각을 하면서 캐시에 도시이름이 없다면 그냥 간단하게 캐시의 0번째 인덱스의 있는 도시이름을 바꿔주면 되겠다고 생각하고, 캐시를 Queue로 구성해서 코드를 짜면 되겠구나라고 생각했습니다. 하지만, 꼭 캐시의 0번째 인덱스가 가장 오랫동안 사용하지 않은 인덱스라고 생각하면 안됐습니다. 예를들어 캐시가 꽉차있을 때 캐시의 첫 번째 인덱스의 도시가 사용되면, 사용횟수는 1번으로 초기화 되고, 나머지 사용횟수는 늘어나기 때문에, 다음의 도시가 캐시에 없다면 꼭 첫 번째가 아닌 나머지 인덱스 중 가장 오랫동안 사용하지 않은 인덱스의 캐시와 교환되기 때문입니다. 그래서 이 부분을 해결하기 위해서 저는 캐시의 각 인덱스의 사용횟수를 알려주는 count 배열을 따로 만들었습니다.

< 문제 풀이 >

1. ArrayList 로 cache 를 만들어 주고, cacheSize 만큼의 count 배열을 사용횟수를 체크하기 위해 선언 합니다.

2. 그리고 문제에서 대소문자 구분이 없다고 했기 때문에, 주어진 cities 의 배열을 모두 소문자/대문자로 통일 시켜줍니다. 저는 소문자로 했지만, 대문자로 해도 상관없습니다.

3. 이제 cities의 크기 만큼 반복문을 실행 하는데, 한번 반복할 때 마다 사용하지 않은 캐시의 도시들에 사용횟수를 카운트 해주는 것을 주의합니다.

①  제일 먼저 cache 에 들어 있는 도시들을 체크하면서 현재 찾고 있는 도시들이 있는지 확인합니다. 만약에 있다면 발견한 것이기 때문에 실행시간(answer) 을 1더해주고, 그 자리에 있는 count 배열의 인덱스도 1로 초기화 시켜줍니다. 그리고 나머지 인덱스의 count 배열도 1씩 더해주고, 다음 도시를 찾기위해 이동합니다. 

② cache에 찾고 있는 도시들이 들어있지 않다면, 두 가지 경우를 확인해야 하는데, cache가 ArrayList 이므로 주어진 cacheSize 와 cache의 크기가 같은지 확인해야합니다. 저는 확실하게 하기 위해서 주어진 조건문에 cache.size() 가 같거나 큰 것으로 설정했습니다. 같다면 이제 cache 가 꽉찬것이기 때문에, cache 에 더이상 도시를 추가할 수 없다는 뜻입니다. 그러므로 가장 사용횟수가 많은 cache 의 도시를 제거하고 그 자리에 현재 찾고 있는 도시를 넣어줍니다. 이 때 마찬가지로 나머지 cache 의 사용 횟수를 1씩 증가시켜 줍니다.

③ cache 가 꽉차지 않았다면, 그냥 다음 cache에 찾고 있는 도시를 넣고, 그 도시의 인덱스의 사용횟수를 1씩 증가시킵니다. 그리고 그 전에 있던 cache 의 사용횟수들 역시 1씩 증가시켜 줍니다.

4. 이렇게 끝까지 cities 배열을 돌고, 실행시간(answer)을 출력하게 되면 답이 나옵니다.

---

import java.util.ArrayList;

class Solution {
  public int solution(int cacheSize, String[] cities) {
      		int answer = 0;
		ArrayList<String> cache = new ArrayList<String>();
		if(cacheSize == 0) {
			answer = 5 * cities.length;
			return answer;
		}
		int[] count = new int[cacheSize];
		
		// 대소문자 구분이 없으므로 모두 소문자로 변환
		for(int i=0; i<cities.length; i++) {
			cities[i] = cities[i].toLowerCase();
		}
		
		
		Outter : for(int i=0; i<cities.length; i++) {
			
			for(int j=0; j<cache.size(); j++) {
				
				if(cache.get(j).equals(cities[i])) {
					
					answer += 1;
					
					count[j] = 1;
					
					for(int k=0; k<cache.size(); k++) {
						if( k != j) count[k]++;
					}
					
					continue Outter;
				}
				
			}
			
			if(cache.size() >= cacheSize) {
				int idx = 0;
				for(int j=0; j<cache.size(); j++) {
					if(count[idx] < count[j]) idx = j;
				}
				cache.set(idx, cities[i]);
				count[idx] = 1;
				
				for(int j=0; j<cache.size(); j++) {
					if(j!=idx) count[j]++;
				}
				
			} else {
				cache.add(cities[i]);
				count[cache.size()-1] = 1;
				
				for(int j=0; j<cache.size(); j++) {
					if(j != cache.size()-1) count[j] ++;
				}
			}
			
//			for(int j=0; j<count.length; j++) {
//				System.out.print(count[j] + " ");
//			}
//			System.out.println();
			
			answer += 5;
		}
		
		return answer;
  }
}