[프로그래머스] 2018 KAKAO BLIND RECRUITMENT 캐시

 

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

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

문제 설명 : 

LRU(Least Recently Used) 를 사용하여 cache 실행시간 구하기

 

문제 풀이 :

LRU는 가장 오랫동안 사용하지 않는 것을 제거하는 알고리즘이다. 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경.

 

1. ArrayList를 캐시크기로 사용하였다. 도시 이름은 대소문자를 구분하지 않기 때문에 모두 대문자로 바꿔주거나 소문자로 바꿔준다.

 

2. cities 배열만큼 돌면서 list에 도시이름이 없으면 cache miss 이므로 실행시간을 5 추가해준다.

 2-1. 만약에 list의 크기가 캐시크기보다 크거나 같으면 가장 오랫동안 참조되지 않은 0번째 인덱스를 삭제해주고, list 맨 뒤에 도시이름을 추가해준다.

 

3. list에 도시이름이 있으면 cache hit이므로 실행시간을 1 추가해준다.

 3-1. 이때 list에서 해당 도시이름의 인덱스를 가져와 삭제해주고, list 맨뒤에 도시이름을 추가해준다.

 

4. 만약 캐시크기가 0이라면 도시이름 배열길이 * 5를 해준다.

import java.util.ArrayList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        ArrayList<String> list = new ArrayList();
    	//캐시 실행시간
        int answer = 0;
        
        if(cacheSize == 0) {
        	answer = cities.length * 5;
        	return answer;
        }
    	    	
    	for (int i = 0; i < cities.length; i++) {
    		//대소문자를 구분하지 않는다.
    		String temp = cities[i].toLowerCase();
    		
    		//list에 도시이름이 있으면
    		if(list.contains(temp)) {
    			answer+= 1;	// hit이므로 실행시간 1
    			int idx = list.indexOf(temp);
    			list.remove(idx);
    			list.add(temp);
    			
    			
    		}else{//도시 이름이 없으면
    			answer+= 5;	// miss이므로 실행시간 5
    			if(list.size() >= cacheSize) list.remove(0);
    			list.add(temp);
    		}
    		
		}
    		
        return answer;
    }

}