[240427] 알고리즘 리부트 55일차 - 프로그래머스 캐시 자바

어떤 자료 구조를 써야할지 고민을 좀 했다. 최악의 경우 십만 개의 도시를 처리해야 하기 때문에 한 번의 반복문 순회로 끝내야 한다고 생각했다. 배열이나 리스트를 사용하기에는 recently used를 처리하기 위해 배열의 인덱스를 당겨줘야 하는 비효율이 있었다. 반대로 링크드리스트를 활용한다면 인덱슬 당기는 처리는 효율적이겠으나 해당 도시가 어느 인덱스에 있는지 처음부터 다 순회해봐야 하는 것이라 또 비효율이 발생했다. 해시맵과 큐를 사용하고자 했으나 큐도 마찬가지로 순서를 당기기 어려웠다. 이를 해결하기 위한 자료구조는 트리맵이라고 생각했고 키에 순서(인덱스)를 넣고 값에 도시이름을 넣어서 존재하는 경우 해당 키를 삭제하고 다시 인덱스와 도시를 map에 넣어줬다. 이를 활용해서 캐시가 다 찼을 경우  가장 예전에 방문한 도시이름을 꺼내서 삭제할 수 있게 된다.트리맵은 키값을 기준으로 오름차순 정렬을 하며 작동하기 때문에 해당 문제를 해결하는 데 효과적일것이라고 생각했다.

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        /** 
        캐시 미스는 캐시에 없을 때 캐시 히트는 캐시에 있을 때
        */
        
        /**
        먼저 들어온 순서를 파악해야 하고        
        있던 도시를 가게 된다면 그 친구를 꺼내서 맨 뒤로 넣어야 함(최근에 사용됨을 보장)
        TreeMap이 맞을 것 같은데 키는 도시명 값은 인덱스         
        캐시 크기는 사이즈로 관리        
        있다면 +1 있던 도시 방문하면 map에서 삭제하고 다시 현재 인덱스로 넣어줌
        없다면 가장 앞에 있는 값 삭제        
        treeMap에 넣을 때 구조는 인덱스와 도시이름으로(lowercase로) 넣고 +5 
        */
        
        TreeMap<Integer, String> cache = new TreeMap<>(); 
        
        if(cacheSize==0){
            answer = cities.length*5;            
        }else{    
            // 도시이름 배열 순환하면서
            for(int i = 0; i<cities.length; i++){

                String thisCity = cities[i].toLowerCase();

                // 존재 여부를 매번 체크
                if(cache.containsValue(thisCity)){ // 이미 존재한다면
                    answer++; // 실행시간 더해주고

                    for(int k : cache.keySet()){
                        if(cache.get(k).equals(thisCity)) {
                            cache.remove(k); // 삭제하고
                            break;
                        }                    
                    }
                    // 다시 넣어줌 -> 맨 뒤로 들어가겠지
                    cache.put(i, thisCity);
                }else{ // 존재하지 않는데
                    answer += 5;

                    // 이미 캐시가 다 찼다면 방문한 지 가장 오래된 도시 삭제  
                    if(cache.size()==cacheSize) {
                        cache.remove(cache.firstKey()); 
                        cache.put(i, thisCity);
                    }
                    // 차지 않았다면
                    else cache.put(i, thisCity); // 현재 도시 넣어줌                                 
                }
            }
        }        
        return answer;
    }
}