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

근데, 캐시가 뭘까요?

캐시(Cache)는 컴퓨터 시스템에서 사용되는 일종의 데이터 저장 공간입니다. 이 저장 공간은 데이터를 빠르게 검색하고 접근하는 데 사용됩니다.

1. CPU 캐시: 이는 CPU와 메인 메모리 사이에 위치한 고속의 데이터 저장 공간입니다. CPU가 자주 접근하는 데이터나 명령어를 저장하고, CPU가 이를 빠르게 가져올 수 있게 합니다. 이로 인해 CPU는 메인 메모리에서 직접 데이터를 가져오는 것보다 훨씬 빠르게 작업을 수행할 수 있습니다.
2. 웹 브라우저 캐시: 웹 브라우저는 사용자가 방문한 웹 페이지의 이미지, 스타일시트, 자바스크립트 파일 등을 로컬 저장소에 저장합니다. 이렇게 하면 사용자가 같은 웹 페이지를 다시 방문할 때 브라우저는 이전에 저장해둔 캐시 데이터를 불러와서 페이지 로딩 시간을 줄일 수 있습니다.
3. 데이터베이스 캐시: 데이터베이스 시스템은 자주 사용되는 쿼리 결과를 캐시에 저장합니다. 이렇게 하면 같은 쿼리가 다시 요청되었을 때 데이터베이스는 실제로 디스크에서 데이터를 읽지 않고 캐시에 저장된 결과를 반환함으로써 응답 시간을 크게 줄일 수 있습니다.

이러한 캐시의 사용은 전체 시스템의 성능을 향상시키는 데 크게 기여하지만, 캐시의 크기가 제한적이기 때문에 어떤 데이터를 캐시에 유지할지, 어떤 데이터를 제거할지 결정하는 "캐시 교체 전략"이 중요합니다. 그리고 이것이 바로 문제에 언급된 LRU(Least Recently Used) 같은 알고리즘이 사용되는 곳입니다.

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        // 캐시의 크기가 0이면 모든 도시를 캐시에서 찾을 수 없으므로 
        // 캐시 미스가 항상 발생합니다. 
        // 따라서 총 실행 시간은 도시의 개수에 5를 곱한 값이 됩니다.
        if(cacheSize == 0) return cities.length * 5;
        
        LinkedList<String> cache = new LinkedList<>();
        int answer = 0;
        
        // 각 도시를 순회하면서 해당 도시가 캐시에 있는지 확인함.
        for (String city : cities) {
            // 대소문자를 구분하지 않기 때문에 
            // 모든 도시 이름을 소문자로 변환
            city = city.toLowerCase();
            
            /*
            cache.remove(city)는 캐시에서 해당 도시를 제거하고, 
            그 도시가 캐시에 있었는지 여부를 반환합니다. 
            따라서 이 코드는 캐시 미스가 발생했는지를 확인하는 조건문임.
            
            캐시 미스가 발생하면 캐시에 도시를 추가하고 
            실행 시간을 5 증가시킵니다. 
            
            만약 캐시가 가득 차 있다면 
            가장 오래된 도시를 제거합니다.
            */
            if (!cache.remove(city)) { // cache miss
                if (cache.size() == cacheSize) {
                    cache.poll();
                }
                answer += 5;
            } else { // cache hit
                answer += 1;
            }
            /*
            캐시 미스가 발생하든, 캐시 히트가 발생하든 
            해당 도시를 캐시에 추가합니다. 
            
            캐시 히트가 발생했다면 
            이전에 캐시에서 해당 도시를 제거했기 때문에 
            다시 추가해야 합니다.
            */
            cache.add(city);
        }

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

        Solution sol = new Solution();
        int result = sol.solution(cacheSize, cities);
        System.out.println(result);
       
    }
}