프로그래머스 lv2 캐시

문제 링크

캐시

풀이

• 다른 조건은 그렇게 어렵지 않았다. 그냥 캐시에 도시 이름 넣고 다음에도 동일한 도시 이름이 나오면 시간 + 1, 아니면 시간 + 5
• 문제는 LRU 알고리즘을 구현해야하는 부분이었다.
• 운영체제 시간에 배웠던 건데, Least Recently Used 알고리즘이라고 페이지 교체시에 가장 오랫동안 사용하지 않은 것부터 교체해주는 알고리즘이다.
• 이는 자바 LinkedList를 사용해서 구현한 deque를 이용해 아주 쉽게 구현할 수 있었다.
  • 만약 deque에 해당 도시 이름이 존재한다면, 존재하는 도시는 deque에서 제거하고, 그 다음에 맨 앞으로 더해준다.
  • 만약 deque에 해당 도시 이름이 없고, deque의 사이즈가 제시된 캐시 사이즈와 동일하다면 가장 뒤에서 하나를 제거해주고, 그 다음에 새로운 도시를 맨 앞에 더해준다.
  • 이때, 제시된 캐시 사이즈가 0인 경우는 해당 로직 내부에서 체크가 불가하므로, 가장 맨 앞에 강제로 도시이름 배열의 길이에 * 5를 해서 리턴해주도록 했다. (불가한 경우 : [seoul, seoul]에 캐시 사이즈 0)
    위의 알고리즘을 통해서 구현한 코드는 다음과 같다.

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        if(cacheSize == 0) return cities.length * 5;
        
        LinkedList<String> cache = new LinkedList<>();

        for (String city : cities) {
            
            city = city.toLowerCase();
            
            if (cache.contains(city)) {
                cache.remove(city);
                cache.addFirst(city);
                answer += 1;
            } else {

                if (cache.size() == cacheSize) {
                    cache.pollLast();
                }

                cache.addFirst(city);
                answer += 5;
            }
        }

        return answer;
    }
}

소감

• LinkedList에는 생각 이상의 다양한 기능이 있다..