[프로그래머스] L2 캐시 / 2018 카카오 블라인드 채용

카카오

[프로그래머스] L2 캐시 / 2018 카카오 블라인드 채용

[풀이]

LRU 리스트를 만든다

1) 리스트에 도시 이름이 존재할 경우(cache hit) => 해당하는 도시 이름을 리스트에서 삭제 후 맨 앞에 다시 추가

2) 리스트에 도시 이름이 존재하지 않은 경우(cache miss) => 리스트에 추가

 

* 캐시 사이즈는 LRU 리스트를 조회할 때 break하는 것으로 해결!

 

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        if(cacheSize==0) return cities.length * 5;
        List<String> LRU = new ArrayList<String>();
        for(int i=0; i<cities.length; i++){
            String city = cities[i].toLowerCase();
            boolean hit = false;
            for(int j=0; j<LRU.size(); j++){
                if(j==cacheSize) break; // cache miss
                if(city.equals(LRU.get(j))){ // cache hit
                    LRU.remove(j);   // cache 삭제
                    LRU.add(0,city); // cache 업데이트
                    answer += 1;
                    hit = true;
                    break;
                }
            }
            if(!hit){ // when cache is missed
                LRU.add(0,city);
                answer += 5;
            }
        }
        return answer;
    }
}