[프로그래머스] 17680. 캐시

문제 링크

[프로그래머스] 17680. 캐시

풀이 과정

LRU(Least Recently Used) 교체 알고리즘을 구현하는 문제입니다. LRU는 교체시 가장 오래전에 사용한 페이지를 교체하는 알고리즘으로, 문제에서 주어진 도시를 최근 언제 사용되었는 지에 대한 정보가 자료구조가 들고 있어야 합니다. 이미 캐시 내에 있는 도시를 재참조할 시에는, 해당 도시를 가장 최근에 사용했다고 갱신을 해줘야 합니다. 따라서 맨 앞 요소만 제거할 수 있는 Queue와 다르게, 인덱스를 이용해 요소 제거가 가능한 LinkedList를 사용했습니다.

if (cacheSize == 0) {
    return cities.length * 5;
}

캐시를 이용하지 못하는 경우, 모두 cache miss 로 간주하고 도시의 총 개수에 cache miss 의 실행 시간 5를 곱하고 그 값을 반환합니다. 캐시를 이용할 수 있는 경우에는 문제에서 주어진 도시 이름 배열을 순회하며, 각 도시를 캐시에 집어넣고 변경하는 과정을 거칩니다.

if (cache.contains(city.toUpperCase())) {
    answer += 1;
    cache.remove(cache.indexOf(city.toUpperCase()));
}

먼저 캐시 내에 해당 도시가 존재하면(cache hit), cache hit 실행 시간인 1을 더해줍니다. cache hit 는 캐시 재참조가 발생한 것을 의미하므로, 캐시 내에서 해당 도시를 제거하고, 리스트의 맨 뒤에 추가합니다. 최근에 사용한 도시일수록, LinkedList 내의 인덱스는 증가합니다.

else {
    answer += 5;

    if (cache.size() == cacheSize)
        cache.remove(0);
}

캐시 내에 해당 도시가 존재하지 않으면(cache miss), cache miss 실행 시간인 5를 더해줍니다. 캐시 내부가 가득 찼으면, 가장 오래전에 참조했다는 걸 의미하는 맨 앞 요소에 해당하는 도시를 제거합니다.

cache.addLast(city.toUpperCase());

위의 과정이 끝나면, 해당 도시 이름의 모든 각각의 문자를 대문자로 바꿔준 뒤 캐시에 추가해줍니다.

코드

import java.util.LinkedList;

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

        LinkedList<String> cache = new LinkedList<>();

        if (cacheSize == 0) {
            return cities.length * 5;
        }

        for (String city : cities) {
            if (cache.contains(city.toUpperCase())) {
                answer += 1;
                cache.remove(cache.indexOf(city.toUpperCase()));

            } else {
                answer += 5;

                if (cache.size() == cacheSize)
                    cache.remove(0);
            }

            cache.addLast(city.toUpperCase());
        }

        return answer;
    }

    public static void main(String[] args) {
        int cacheSize = 3;
        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};

//        int cacheSize = 3;
//        String[] cities = {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};

//        int cacheSize = 2;
//        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

//        int cacheSize = 5;
//        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

//        int cacheSize = 2;
//        String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};

//        int cacheSize = 0;
//        String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};

        solution(cacheSize, cities);
    }
}