[프로그래머스/Java] 캐시

 

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

---

처음 코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return 5 * cities.length;
        }
        
        Deque<String> deque = new ArrayDeque<>();
        Set<String> set = new HashSet<>();
        int answer = 0;
        
        for (String c : cities) {
            String city = c.toLowerCase();
            int qsize = deque.size();
            
            /** cache hit **/
            if (set.contains(city)) {
                answer++;
                
                // 다른 요소들 다시 다 추가해주고
                for (int j=0; j<qsize; j++) {
                    String q = deque.poll();
                    if (!q.equals(city)) {
                        deque.add(q);
                    }
                }
                
                // 마지막에 현재 들어온 입력 추가
                deque.add(city);
                continue;
            }
            
            /** cache miss **/
            // 현재 캐시가 다 차있는 경우 빼주고
            if (qsize >= cacheSize) {
                String q = deque.poll();
                set.remove(q);
            }
            
            // 현재 들어온 입력 추가
            deque.add(city);
            set.add(city);
            answer += 5;
        }
        
        return answer;
    }
}

 

처음에 PriorityQueue 이용해서 풀었다가 생각해보니 어차피 실행 순서를 저장하는데, 우선순위 큐가 필요 없었다. Deque로 변경

또, Map 이용했다가 값이 몇 번 나타났는지도 필요가 없었다. Set으로 변경

 

제출 후 다른 풀이들을 보니 다들 너무 깔끔하게 푼 것이 아닌가...!! 저것도 많이 고친 거였는데..ㅠㅠㅋㅋ

큐 자체에서 contains, remove 할 생각을 전혀 못했다.

 

---

 

변경 코드

 

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return 5 * cities.length;
        }
        
        Deque<String> deque = new ArrayDeque<>();
        int answer = 0;
        
        for (String c : cities) {
            String city = c.toLowerCase();
            
            /** cache hit **/
            if (deque.contains(city)) {
                deque.remove(city);
                deque.add(city);
                answer++;
                continue;
            }
            
            /** cache miss **/
            if (deque.size() >= cacheSize) {
                deque.poll();
            }
            deque.add(city);
            answer += 5;
        }
        
        return answer;
    }
}

 

훨씬 깔끔해졌다.

 

 

차이는 미미하지만 평균 실행 시간도 줄어들었다.