[프로그래머스] 캐시

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17680

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

나의 풀이

먼저 캐시 교체 알고리즘 중 LRU(Least Recently Used)에 대한 이해가 필요했다.

 

쉽게 LRU알고리즘은 가장 오랫동안 사용되지 않은 대상이 삭제되는 개념이다.

 

예를 들어 1,2,3 이 삽입되었다면

 

3 2 1

 

여기서 2가 추가되면

 

2 3 1

 

여기서 1 이추가 되면

 

1 2 3

 

여기서 5가 추가되면, 가장 오랫동안 사용되지 않았던 3이 삭제되고, 5를 삽입하게 되는 것이다.

 

5 1 2

 

LRU알고리즘을 처리하기 위해서 먼저 Cache를 보관하기 위한 LinkedHashMap ( cacheBox ),

Cache의 우선순위를 기록하기 위한 LinkedList ( cacheBox2 )를 사용하였다.

 

처리 대상 도시가 Map 있다면 캐시에 존재, 없다면 미존 재하는 것이다.

 

캐시에 존재하지 않을 때는 2가지의 처리 조건이 존재한다.

 

- 캐시에 없을 때 조건 1

 

Map의 크기가 입력값 cacheSize보다 작다면 put 하는 작업만 해준다.

 

- 캐시에 없을 때 조건 2

 

Map의 크기가 cacheSize인 경우이다. ( else )

 

이 경우에는 새로운 city를 put 하고 가장 오래된 대상을 remove 해준다.

 

이때 가장 오래된 대상은 cacheBox2의 0번째 값이 된다. ( cacheBox2는 계속 우선순위를 유지하고 있다. )

 

다음은 캐시에 존재하는 경우의 조건이다.

 

현재 처리 중인 city가 캐시에 존재한다면 우선순위를 1등으로 올려주어야 한다.

 

LinkedList는 add 한 순서를 유지하므로 현재 도시가 어디에 있든 상관없이, 기존의 데이터를 지우고 다시 맨 마지막 index에 존재하도록 해주면 된다.

 

이때 remove대상은 index가 아닌 object값으로 한다. ( 해당 city를 직접 제거 )

 

마지막으로 입력값 cacheSize가 0인 경우에는 모든 city의 실행시간은 5가 됨으로 해당 조건을 따로 처리해주면 된다.

코드

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

		// 캐시율이 0인경우
		if( cacheSize == 0 ) return 5*cities.length;

		Map<String,Integer> cacheBox = new LinkedHashMap<String,Integer>();	
		List<String> cacheBox2 = new LinkedList<String>();

		for ( int i = 0 ; i < cities.length; i++ ) {

			String city = cities[i].toUpperCase();

			int time = 5;
			
			if( cacheBox.get(city) == null ) {
				
				// cacheSize보다 작으면 add는 필수.
				if ( cacheBox.size() < cacheSize ) {
					cacheBox.put(city,1);
					cacheBox2.add(city);
				}else { // cacheSize인 경우에는 우선순위만 변경
					cacheBox.put(city,1);
					cacheBox2.add(city);

					cacheBox.remove(cacheBox2.get(0));
					cacheBox2.remove(0);
				}
			}else { // cache에 있던것을 또 접근해주었을때는 우선순위가 변경되어야 한다.
				time=1;
				cacheBox2.remove(city); // object로 제거가능
				cacheBox2.add(city);
			}
				
				answer+=time;
			}

		return answer;
	}

제출 결과