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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

문제에서 주어준대로 구현하면 되는 문제다.

최대 100,000개의 문자열로 이루어진 문자열 배열 주어지고, 실행 시간을 계산해야 한다.

이때 캐시가 존재하며, 캐시 사이즈의 범위는 1~30이다. 캐시 히트 시 실행 시간은 1, 캐시 미스 시 실행 시간은 5다. 이때 캐시 교체 알고리즘으로 LRU를 사용한다.

LRU는 가장 많이 히트된 블록을 최우선으로 캐싱하는 캐시 교체 전략이다.

 

풀이

처음엔 캐시의 자료구조를 LinkedHashSet으로 구현하려고 했었다. 예전 임베디드운영체제 수업에서 BufferCache를 구현하는 팀 프로젝트를 진행했을 때 캐시를 연결 리스트로 구현했던 것이 기억이 났다.

 

하지만 Set의 첫 번째 요소를 제거해 본 적은 없어서 어떻게 구현할 수 있을지 고민해 본 결과, 마땅한 방법이 생각나지 않았고 캐시의 사이즈가 그리 크지 않았기 때문에 ArrayList로도 충분히 해결할 수 있을 것이라 판단했다. 가능하면 연결 리스트를 사용하는 것이 ArrayList를 사용하는 것보다 효율적이다. ArrayList의 contains 메서드나 remove 메서드는 연산에 O(n) 시간이 걸리기 때문이다.

 

Set은 기본적으로 인덱스를 제공하지 않는다. Set의 첫 번째 요소를 제거하기 위해선 iterator를 사용해야 한다. iterator의 next 메서드를 한 번만 사용하면 첫 번째 요소를 얻을 수 있다.

Set<String> set = new LinkedHashSet<>();
if (set.iterator.hasNext()) {
    String first = iterator.next();
    set.remove(first);
}

 

코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int executionTime = 0;
        
        List<String> cache = new ArrayList<>();
        for (int i = 0; i < cities.length; i++) {
            String currentCity = cities[i].toLowerCase();
            if (cache.contains(currentCity)) {
                executionTime += 1;
            } else {
                executionTime += 5;
            }
            LRU(cache, cacheSize, currentCity);
        }
        
        return executionTime;
    }
    
    public static void LRU(List<String> cache, int cacheSize, String city) {
        if (cacheSize == 0) return;
        if (cache.size() < cacheSize) {
            cache.add(city);
        } else {
            if (cache.contains(city)) {
                cache.remove(city);
                cache.add(city);
            } else {
                cache.remove(0);
                cache.add(city);
            }
        }
    }
    
}