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

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

프로그래머스

[1차] 캐시 알고리즘 설명

 

문제 설명

캐시 메모리에서의 작업 처리 시간 최적화를 위해, Least Recently Used (LRU) 알고리즘을 사용하여 캐시 히트와 캐시 미스를 관리하는 문제다. 캐시 크기와 도시 이름 배열이 주어졌을 때, 각 도시 이름이 주어질 때마다 캐시 히트인지 미스인지 판단하고 총 실행 시간을 계산한다.

 

해결 방법

1. 기본 설정:
   • cacheSize가 0이면 모든 요청이 캐시 미스이므로 도시 수에 5를 곱한 값을 반환한다.
   • 도시 이름을 대문자로 변환하여 처리한다.

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

2. 미리 사전에 갈 수 있는 도시들을 셋팅한다:

   for (int i = 0; i < cities.length; i++) {
       String key = cities[i].toUpperCase(); // 대문자로 변환
       if (dict.getOrDefault(key, -1) == -1) {
           dict.put(key, 0);
       }
   }

3. 도시들을 순회하면서 해당 도시가 사전에서 0인지 1인지 확인한다:
   • 도시가 캐시에 없으면 (캐시 미스):
     • 실행 시간에 5를 더한다.
     • 캐시가 꽉 찼다면 가장 오래된 도시를 제거한다.
     • 현재 도시를 캐시에 추가한다.
   • 도시가 캐시에 있으면 (캐시 히트):
     • 실행 시간에 1을 더한다.
     • 도시를 큐에서 제거하고 다시 추가하여 최신 상태로 만든다.

   for (int i = 0; i < cities.length; i++) {
       String city = cities[i].toUpperCase(); // 대문자로 변환
       
       if (dict.get(city) == 0) { // 캐시 미스
           dict.put(city, 1); // 캐시에 저장
           answer += 5; 
           
           if (LRUqueue.size() == cacheSize) { // 캐시 큐가 꽉 찼다면 오래된 캐시 삭제
               String cache = LRUqueue.poll();
               dict.put(cache, 0); 
           }
           LRUqueue.add(city); // 캐시 큐에 저장
       } else { // 캐시 히트
           answer += 1;
           LRUqueue.remove(city);
           LRUqueue.add(city);
       }
   }

전체 코드 구현

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> LRUqueue = new LinkedList<>();
        Map<String, Integer> dict = new HashMap<>();
        
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        for (int i = 0; i < cities.length; i++) {
            String key = cities[i].toUpperCase(); // 대문자로 변환
            if (dict.getOrDefault(key, -1) == -1) {
                dict.put(key, 0);
            }
        }
        
        for (int i = 0; i < cities.length; i++) {
            String city = cities[i].toUpperCase(); // 대문자로 변환
            
            if (dict.get(city) == 0) { // 캐시 미스
                dict.put(city, 1); // 캐시에 저장
                answer += 5; 
                
                if (LRUqueue.size() == cacheSize) { // 캐시 큐가 꽉 찼다면 오래된 캐시 삭제
                    String cache = LRUqueue.poll();
                    dict.put(cache, 0); 
                }
                LRUqueue.add(city); // 캐시 큐에 저장
            } else { // 캐시 히트
                answer += 1;
                LRUqueue.remove(city);
                LRUqueue.add(city);
            }
        }
        
        return answer;
    }
}