[프로그래머스] [1차] 캐시

코드 힌트

문제 이해:

• 이 문제는 LRU (Least Recently Used) 캐시 알고리즘을 구현하는 것입니다. LRU 캐시는 가장 오랫동안 사용되지 않은 페이지(도시)를 교체하는 방식입니다.
• 주어진 cities 배열을 순차적으로 처리하면서, 각 도시에 대한 참조 여부에 따라 실행 시간을 계산해야 합니다.

LRU 캐시 설명:

• LRU 캐시는 한정된 크기의 메모리를 효율적으로 사용하기 위한 알고리즘입니다.
• 캐시에 있는 항목 중 가장 오랫동안 사용되지 않은 항목을 교체합니다.
• 캐시에 도시가 있으면 hit으로 간주하고 실행 시간에 1초를 더합니다.
• 캐시에 도시가 없으면 miss로 간주하고 실행 시간에 5초를 더합니다.

캐시 구현:

• 저는 캐시를 List로 구현했습니다. 리스트의 인덱스가 낮을수록 오랫동안 참조되지 않은 도시입니다.
• HashMap이든 우선순위를 저장할 수 있는 방법이 있다면 어떤 자료구조라도 상관없습니다.
• 캐시에 도시가 있으면 해당 항목을 제거한 후 리스트의 끝에 추가하여 최근에 참조된 것으로 업데이트합니다.
• 캐시에 도시가 없으면 새로운 도시를 리스트의 끝에 추가합니다. 만약 캐시가 가득 차면 가장 앞에 있는 도시를 제거합니다.

알고리즘:

1. cacheSize만큼의 공간을 가지는 캐시를 구현하기 위해 List를 사용합니다.
2. cities 배열을 순차적으로 순회하며 도시 이름을 소문자로 변환한 후, 캐시에 해당 도시가 있는지 확인합니다.
3. 도시가 캐시에 있다면, 그 도시를 캐시에서 제거한 후, 리스트의 끝에 추가하여 참조를 갱신합니다. 실행 시간에 1초를 더합니다.
4. 도시가 캐시에 없다면, 리스트의 끝에 도시를 추가하고, 실행 시간에 5초를 더합니다.
5. 만약 캐시가 가득 찼다면, 리스트의 첫 번째 요소를 제거하여 가장 오랫동안 참조되지 않은 도시를 제거합니다.
6. 모든 처리가 끝난 후 총 실행 시간을 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        // 실행 시간
        int result = 0;
        
        // 캐시 (index가 0에 가까울 수록 오랫동안 참조하지 않음)
        List<String> cache = new ArrayList<>();
        
        // cities배열을 순차적으로 실행
        for (String city : cities) {
            // 도시 이름을 소문자로 변환
            city = city.toLowerCase();
            int idx = cache.indexOf(city);
            
            // 캐시에 저장된 도시일 때 (Hit)
            if (idx >= 0) {
                cache.remove(idx);  // 캐시에서 요소 삭제 후 추가
                cache.add(city);    
                result += 1;  // 실행 시간 1초 추가
            } 
            // 캐시에 없는 도시일 때 (Miss)
            else {
                cache.add(city);
                result += 5;  // 실행 시간 5초 추가
            }
            
            // 캐시가 저장할 수 있는 크기를 초과했을 때
            if (cache.size() > cacheSize) {
                cache.remove(0);  // 가장 오랫동안 참조하지 않은 도시 삭제
            }
        }
        
        // 총 실행 시간 반환
        return result;
    }
}