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

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 

프로그래머스

[풀이]

우선 문제를 풀기 위해서 LRU 교체 알고리즘에 대해서 알아야 했습니다.

LRU는 Least Recently Used의 약자로, 즉 가장 오랫동안 참조되지 않은 캐시를 교체하는 방식입니다.

만약 캐시의 여유 저장공간이 없고, 캐시에 해당 값이 없다면 가장 오랫동안 사용되지 않았던 캐시를 교체하는 것입니다.

 

따라서 캐시가 참조된 시간별로 데이터를 관리하고 싶어서 LinkedList<String> cache를 통해 캐시를 관리하였습니다. 만약 이미 캐시에 있는 값을 사용했다면 중간에 있는 캐시를 맨 마지막으로 이동시켜야 하므로 LinkedList가 적합하다고 생각했습니다.

 

cities[]를 탐색하며, 해당 city가 캐시에 존재하지 않고, 만약 캐시의 여유 저장공간이 없다면 가장 앞 노드를 삭제하고 마지막 노드에 city를 추가하였습니다. 또한, 만약 city가 존재한다면 cache.indexOf(city)를 통해 해당 city의 index의 값을 찾아 삭제하고 마지막 노드에 도시를 추가해주었습니다.

 

[코드]

import java.util.*;
class Solution {
    public static int time = 0;
    public static LinkedList<String> cache = new LinkedList<String>();
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        if(cacheSize == 0) {
            answer = cities.length*5;
        } else {
            for(int i=0;i<cities.length;i++) {
                String city = cities[i].toLowerCase();
                int index = cache.indexOf(city);
                // 해당 도시가 존재하지 않음
                if(index == -1) {
                    if(cache.size() == cacheSize) {
                        cache.removeFirst();
                    }
                    answer += 5;
                } else {
                    cache.remove(index);
                    answer++;
                }
                cache.addLast(city);
            }
        }
        return answer;
    }
}