캐시_복습

2026.07.23

문제 풀이

1차 실행 오류

---

90/100

실패

---

실패 원인 분석

cacheSize == 0일 때,
캐시에 하나의 데이터가 저장이 되는 경우의 수를 고려하지 않음

---

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int runTime = 0;
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < cities.length; i++) {
            for (String key : map.keySet()) { // 캐시 갱신
                map.put(key, map.get(key) + 1);
            }
            
            String city = cities[i].toUpperCase();
            if (map.get(city) == null) { // cache miss 일 때
                runTime += 5;
                if (map.size() >= cacheSize) { // cache가 다 찼을 때
                    String removeCity = "s";
                    int min = 0;
                    for (String key : map.keySet()) {
                        if (map.get(key) > min) {
                            removeCity = key;
                            min = map.get(key);
                        }
                    }
                    map.remove(removeCity); // 가장 오래 전에 사용한 캐시 삭제
                }
                map.put(city, 0); // 새로운 캐시 삽입
            }
            else {
                runTime++;
                map.put(city, 0); // 사용한 캐시 초기화
            }
        }
        return runTime;
    }
}

나의 코드

---

소요 시간: 23분
시간 복잡도: $O(n)$

---

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) {
            return 5 * cities.length;
        }
        int runTime = 0;
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < cities.length; i++) {
            for (String key : map.keySet()) { // 캐시 갱신
                map.put(key, map.get(key) + 1);
            }
            
            String city = cities[i].toUpperCase();
            if (map.get(city) == null) { // cache miss 일 때
                runTime += 5;
                if (map.size() >= cacheSize) { // cache가 다 찼을 때
                    String removeCity = "s";
                    int min = 0;
                    for (String key : map.keySet()) {
                        if (map.get(key) > min) {
                            removeCity = key;
                            min = map.get(key);
                        }
                    }
                    map.remove(removeCity); // 가장 오래 전에 사용한 캐시 삭제
                }
                map.put(city, 0); // 새로운 캐시 삽입
            }
            else {
                runTime++;
                map.put(city, 0); // 사용한 캐시 초기화
            }
        }
        return runTime;
    }
}

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

LinkedList를 사용하여 순서를 유지한 채 해시를 유지
캐시가 사용되면 기존 캐시를 뺀 후 재삽입

---

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return 5 * cities.length;

        int runTime = 0;
        LinkedList<String> cache = new LinkedList<>();

        for (String city : cities) {
            String upper = city.toUpperCase();
            if (cache.remove(upper)) {   // hit: 기존 원소 제거 후 뒤에 재삽입
                runTime += 1;
            } else {                     // miss
                runTime += 5;
                if (cache.size() >= cacheSize) {
                    cache.pollFirst();   // 가장 오래된 것 제거 (LRU)
                }
            }
            cache.addLast(upper);        // 최근 사용으로 갱신
        }
        return runTime;
    }
}

문제 해결 후기

익숙하지 않았던 해시 사용을 점점 능숙하게 사용하고 있다는 생각이 든다.
동시에 LinkedList와 같은 다양한 해시들도 고루고루 활용해가며
적재적소에 활용하는 능력을 키워야겠다고 생각했다.