[알고리즘]프로그래머스 17680번 - [1차]캐쉬

프로그래머스 17680번 - [1차]캐쉬

프로그래머스 17680번 - https://programmers.co.kr/learn/courses/30/lessons/17680

 

요구사항

1. LRU 캐시 교체 알고리즘을 기반으로 주어진 도시 이름들을 조회할 때 걸리는 실행 시간을 측정하여 반환하라.

2. 캐시 히트(cache hit) 일 경우 실행시간은 1, 캐시 미스(cache miss) 일 경우 실행시간은 5이다.

 

요구사항 분석 및  풀이과정

LRU 캐시 교체 알고리즘은, 캐시의 크기가 꽉 찼을 경우 가장 오래된 캐시 데이터를 삭제하고, 새로운 데이터를 캐싱하는 알고리즘입니다. 자세한 알고리즘이 궁금하다면 여기를 참고해주세요.

 

우리는 LRU 캐시 교체 알고리즘을 리스트를 이용하여 구현할 것입니다.

리스트의 가장 앞부분은 캐시에 가장 오래된 데이터가 존재하며, 가장 뒷부분으로 갈수록 최근에 캐시에 저장된 데이터가 존재하는 방식입니다.

 

리스트는 캐시에 가장 오래된 데이터를 삭제할 때 성능을 위하여 ArrayList 가 아닌, LinkedList를 사용합니다.

ArrayList를 사용할 경우 리스트의 첫 원소를 제거할 경우 뒤의 원소가 위치 재배열이 발생하기 때문입니다.

 

1-1. 도시 이름을 조회하였을 때 이미 캐시에 존재한다면, 캐시 히트이며 실행시간은 1을 누적합니다.

1-2. 해당 도시는 방금 캐싱되었기 때문에 현재 위치한 위치에서 제거하여, 리스트의 가장 뒷부분에 추가합니다.

 

2-1. 만약 캐시에 존재하지 않는다면, 캐시 미스이며 실행시간은 5를 누적합니다. 그런 후 현재 캐시의 크기를 확인합니다.

2-2. 주어진 캐시 사이즈를 넘지 않았다면, 캐싱할 자리가 남았으므로 캐싱을 위하여 리스트의 가장 뒷부분에 추가합니다.

2-3. 만약 캐시 사이즈를 넘어 캐시에 공간이 없다면, 가장 오래된 데이터(리스트의 첫 원소)를 리스트에서 제거한 후 캐싱합니다.

 

주의하여할 점은 도시 이름은 대소문자를 구분하지 않습니다. 통일(대문자 또는 소문자)하는 것이 편합니다.

소스코드 작성

import java.util.Deque;
import java.util.LinkedList;

class Solution {

    public int solution(int cacheSize, String[] cities) {
        Deque<String> cache = new LinkedList<>();
        
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        for(int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toUpperCase();
        }
        
        int result = 0;
        for(String city : cities) {
            if (cache.contains(city)) {
                cache.remove(city);
                cache.addLast(city);
                result += 1;
            } else {  
                if (cache.size() == cacheSize) {
                    cache.removeFirst();
                }
                cache.addLast(city);
                result += 5; 
            }
        }
        
        return result;
    }
}

 

결과

 

소스코드 깃허브 주소

링크