[프로그래머스] [1차] 캐시 (JAVA)

🗒️알고리즘 분류

#구현 #implementation

📌기억해야 할 포인트

문제에서 다양한 캐시 알고리즘 중 LRU(Least Recently Used)를 사용한다.

• 캐시가 캐시 사이즈에 따라서 저장할 수 있는 양이 달라지기 때문에 캐시 사이즈가 얼마인지 잘 확인해야 한다.
• Java 의 Collection 중 어느 것을 사용할지 고민했다.
  • 처음엔 요소의 중복을 없애야겠다고 생각해서 HashSet 을 사용했다. 하지만 Cache 에 들어가는 순서가 중요한 것을 깨달았다.
  • ArrayDeque 를 사용해서 CacheHit, CacheMiss 상황에 따라서 pollLast(), offerFirst(e) 를 해주었다. 하지만, CacheHit 이면 해당 요소를 캐시의 맨 뒤로 보내주는 작업을 관과하고 있었다. ArrayDeque 는 인덱스 기반 접근이 불가하다.
  • 맨 앞의 작업이 빈번한 것을 깨닫고 최종적으로 List 중 LinkedList 를 사용해서 문제를 해결했다.
  • 아래는 LinkedList 에서 사용한 주요 메서드이다.
    • E e = list.remove(index);
    • int index = list.indexOf(e);
    • boolean b = list.contains(e);
• CacheSize 가 0 일 수도 있다. 문제 조건을 제대로 읽자!

📝풀이 코드(JAVA)

import java.util.*;

class Solution {
    private List<String> cache = new LinkedList<>();
    private int answer = 0;
    
    public int solution(int cacheSize, String[] cities) {        
        for (String city : cities) {
            String c = city.toLowerCase();
            
            if (isCacheHit(c)) {
                cacheHit(c);
            } else {
                cacheMiss(c, cacheSize);
            }
        }
        
        return answer;
    }
    
    private void cacheHit(String city) {
        String removed = cache.remove(cache.indexOf(city));
        cache.add(removed);
        ++answer;
    }
    
    private void cacheMiss(String city, int cacheSize) {
        if (!cache.isEmpty() && cache.size() >= cacheSize) {
            cache.remove(0);
        }
        if (cacheSize > 0) {
            cache.add(city);            
        }
        answer += 5;
    }
    
    private boolean isCacheHit(String city) {
        return cache.contains(city);
    }
}

⏰총 풀이시간

• 30분