캐시 [프로그래머스]

1) 문제 접근 방법

- 캐시 사이즈가 0인 경우는, cities의 길이에 5 곱한 값을 반환합니다.

-> 왜냐면, cache hit이 발생할 수 없고, 매번 cache miss가 발생하기 때문입니다. 

- 캐시 사이즈가 0이 아닌 경우는,

   (1) map이 city를 포함하고 있는 경우에는, cache hit이므로 answer에 1을 더하고, 최신 방문 idx를 업데이트합니다. 

   (2) map이 city를 포함하고 있지 않은 경우에는,

     (2-1) map이 꽉 차지 않았다면, 그냥 map에 도시명과 최신 idx를 추가합니다.

     (2-2) map이 꽉 차 있다면, map의 keySet()을 통해 map을 순회하면서, lru인 string을 찾습니다.

     -> lru인 string을 찾는 기준은, 가장 idx(value값)가 낮은 string입니다.  

     -> idx가 낮다는 것은 가장 오래 전에 사용된 것이라는 의미이기 때문입니다. 

     (2-3) 그 다음에 해당 lru를 map에서 제거해준 다음에, 새로운 city를 map에 idx와 함께 추가합니다. 

     (2-4) map이 city를 포함하고 있지 않으므로, cache miss이고 answer에 5를 더해줍니다. 

import java.util.*; 

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        HashMap<String, Integer> map = new HashMap<>(); 
        
        if(cacheSize == 0){
            return 5*cities.length;
        }else{
            
            for(int i=0; i<cities.length; i++){
                String city = cities[i].toLowerCase();
                
                if(map.containsKey(city)){
                    answer += 1;
                    map.put(city, i);
                }else{
                    if(map.size()== cacheSize){
                        int minPos = Integer.MAX_VALUE; 
                        String lru = "";
                        for(String str: map.keySet()){
                            int pos = map.get(str);
                            if(pos <= minPos){
                                minPos = pos;
                                lru = str;
                            }
                        }
                        map.remove(lru);
                        map.put(city, i);
                    }else{
                        map.put(city, i);
                    }
                    answer += 5;
                }
            }
        }
        
        return answer;
    }
}