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

문제

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

문제풀이 방법

- 캐시 크기가 0인 경우, 모든 접근이 캐시 미스로 처리되므로 도시 수에 5를 곱한 값을 바로 반환
- 캐시를 LinkedList로 구현 -> WHY? LinkedList는 항목의 추가 및 제거가 용이하여 LRU 캐시 구현에 적합
- 대소문자 구별을 하지 않기 위해 모두 대문자로 변경

- 캐시 히트: 도시 이름이 캐시에 있는 경우, 
	캐시에서 해당 도시 이름을 제거하고 다시 추가
	이를 통해 해당 항목이 최신으로 갱신
	실행시간 + 1
- 캐시 미스: 도시 이름이 캐시에 없는 경우,
  실행 시 + 5
  캐시가 가득 찬 경우 가장 오래된 항목을 제거하고 새로운 도시 이름을 추가

💡 예제 풀이

• 캐시 크기: 3
• 도시 이름 배열: ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]

1. 초기 설정:
   • 캐시 크기: 3
   • 도시 이름 배열: ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]
   • 총 실행 시간: 0
2. 도시 이름 처리:
   • "Jeju" (미스): 캐시에 추가 ["JEJU"], 실행 시간 5
   • "Pangyo" (미스): 캐시에 추가 ["JEJU", "PANGYO"], 실행 시간 10
   • "Seoul" (미스): 캐시에 추가 ["JEJU", "PANGYO", "SEOUL"], 실행 시간 15
   • "NewYork" (미스): 캐시에서 가장 오래된 "Jeju" 제거 후 추가 ["PANGYO", "SEOUL", "NEWYORK"], 실행 시간 20
   • "LA" (미스): 캐시에서 가장 오래된 "Pangyo" 제거 후 추가 ["SEOUL", "NEWYORK", "LA"], 실행 시간 25
   • "Jeju" (미스): 캐시에서 가장 오래된 "Seoul" 제거 후 추가 ["NEWYORK", "LA", "JEJU"], 실행 시간 30
   • "Pangyo" (미스): 캐시에서 가장 오래된 "NewYork" 제거 후 추가 ["LA", "JEJU", "PANGYO"], 실행 시간 35
   • "Seoul" (미스): 캐시에서 가장 오래된 "LA" 제거 후 추가 ["JEJU", "PANGYO", "SEOUL"], 실행 시간 40
   • "NewYork" (미스): 캐시에서 가장 오래된 "Jeju" 제거 후 추가 ["PANGYO", "SEOUL", "NEWYORK"], 실행 시간 45
   • "LA" (미스): 캐시에서 가장 오래된 "Pangyo" 제거 후 추가 ["SEOUL", "NEWYORK", "LA"], 실행 시간 50
3. 결과 반환:
   • 총 실행 시간: 50

나의 코드

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int totalTime = 0;
        
        // 캐시 크기가 0이면 모든 도시에서 캐시 미스 발생 -> 도시 수 * 5 반환
        if (cacheSize == 0) {
            return cities.length * 5; 
        }

        LinkedList<String> cache = new LinkedList<>(); 
        
        for (String city : cities) { 
            String cityUpper = city.toUpperCase(); // 대소문자 구분하지 않기 위해
            
            if (cache.remove(cityUpper)) { // 캐시 리스트에서 해당 도시 이름 제거 (캐시 히트 시)
                totalTime += 1; // 캐시 히트 시 실행 시간은 1
            } else { // 캐시 리스트에서 해당 도시 이름을 찾지 못한 경우 (캐시 미스 시)
                totalTime += 5; // 캐시 미스 시 실행 시간은 5
                if (cache.size() >= cacheSize) { // 캐시가 가득 찬 경우
                    cache.removeFirst(); // 가장 오래된 항목 제거 (LRU 방식)
                }
            }
            cache.add(cityUpper); // 캐시 리스트에 현재 도시 이름 추가 (히트든 미스든 항상 추가)
        }

        return totalTime; 
    }
}