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

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toLowerCase();
            if (cache.contains(city)) {
                cache.remove(city);
                cache.addFirst(city);
                answer += 1;
            } else {
                if (cache.size() >= cacheSize) {
                    if (!cache.isEmpty()) {
                        cache.removeLast();
                    }
                }
                cache.addFirst(city);
                answer += 5;
            }
        }
        return answer;
    }
}

LRU라는 알고리즘을 처음 보면 상당히 당황스러운 문제이다. 하지만 LRU라는 알고리즘이 그렇게 어려운 내용이 아니여서 이해하기가 쉽다. 문제 풀다가 고민 되는점은 중간에 있는 도시를 어떻게 없애고 첫번째에 삽입하는 점이다.

일반적으로 코딩테스트에 스택, 큐, 덱을 이용해서 문제를 푸는데 그걸 이용해서 이번 문제를 풀기에는 상당히 부담스럽다. 원래 스택, 큐, 덱 모두 처음이나 마지막 값을 제거하고 삽입하는 방식이라 이 문제랑은 맞지 않은 느낌이다.

그럴 때 이용할 수 있는게 LinkedList이다. LinkedList는 노드들의 연결 관계만 이용해서 중간에 값을 없애고 삽입하기 좋은 자료구조이다. 중간에 값을 없애고 노드끼리 새로 연결만 해주면 되는데 LinkedList의 remove가 알아서 연결해준다. 그래서 손쉽게 이번 문제를 접근 할 수 있다.

고민되는 점은 LinkedList의 contains을 이용하여 검색하는 과정인데 시간 복잡도가 O(n)인 선형 복잡도 방식이라 캐시의 크기가 커지면 조금 불리할 것 같다.

근데 캐시가 대용량인게 원래 이상한거 아님?
그래서 contains로 검색해도 괜찮을 것 같다.