[프로그래머스] 1차 캐시 - 다양한 자료구조 풀이!

0️⃣ 문제 링크

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

school.programmers.co.kr

1️⃣ 문제 설명

LRU(Least Recently Used) 캐시를 구현하는 문제이다.
캐시 크기 cacheSize와 도시 이름 배열 cities가 주어진다.

• 캐시에 도시가 있으면 cache hit (1초)
• 캐시에 없으면 cache miss (5초)
• 캐시는 LRU 정책으로 동작한다.
• 도시 이름은 대소문자를 구분하지 않는다.

2️⃣ 문제 접근 방식

• 캐시 자료구조
  • LinkedList<String> 사용
  • 가장 오래 사용되지 않은 데이터는 리스트의 앞
  • 가장 최근에 사용된 데이터는 리스트의 뒤
• 처리 방식
  • 도시 이름을 모두 소문자로 변환
  • 캐시에 도시가 존재하는 경우, 해당 도시 제거 후 리스트 맨 뒤에 다시 추가 (최근 사용)
  • 캐시에 도시가 존재하지 않는 경우, 캐시가 가득 찼다면 맨 앞 요소 제거 후 새 도시를 리스트 맨 뒤에 추가

시간 복잡도 : O(N × cacheSize)
(cacheSize ≤ 30 이므로 충분히 통과 가능)

3️⃣ 전체 코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

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

        List<String> cache = new LinkedList<>();

        for (String c : cities) {
            String city = c.toLowerCase();

            if (cache.contains(city)) {
                cache.remove(city);
                cache.add(city);
                answer += 1; // cache hit
            } else {
                if (cache.size() >= cacheSize) {
                    cache.remove(0); // LRU 제거
                }
                cache.add(city);
                answer += 5; // cache miss
            }
        }

        return answer;
    }
}

4️⃣ 다른 풀이 코드

• 캐시 자료구조
  • LinkedHashMap 사용 (내부적으로 HashMap + Doubly Linked List 구조)
• accessOrder = true 옵션 사용 (접근 순서 기반 정렬)
  • get() / put() 시 접근한 엔트리가 자동으로 맨 뒤로 이동
  • 가장 앞의 엔트리는 가장 오래 사용되지 않은 데이터(LRU) 가 됨
• removeEldestEntry() → 캐시 초과 시 자동 제거

시간 복잡도 : O(N)

import java.util.*;

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

        int answer = 0;

        // 생성자 파라미터 (초기 용량, load factor, 접근 순서 사용)
        // load factor(부하 계수) : 해시 테이블이 언제 확장될지 결정하는 기준 값
        Map<String, String> cache =
            new LinkedHashMap<String, String>(cacheSize, 0.75f, true) {
                // put() 이후 자동 호출 (true 반환 시 가장 오래된 요소 제거)
                @Override
                protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                    return size() > cacheSize;
                }
            };

        for (String c : cities) {
            String city = c.toLowerCase();

            if (cache.containsKey(city)) {
                answer += 1; // cache hit
            } else {
                answer += 5; // cache miss
            }
            cache.put(city, city); // 접근 시 자동으로 최신화
        }

        return answer;
    }
}

5️⃣ 회고 및 배운점

이번 문제를 통해 LRU(Least Recently Used) 캐시의 동작 원리를 명확히 이해할 수 있었다.
단순히 “가장 오래 안 쓴 데이터를 제거한다”는 개념이 아니라, 접근 시점(get / put)에 따라 순서가 어떻게 바뀌는지까지 구체적으로 알게 되었다.
또한 LinkedHashMap이라는 자료구조가 단순히 순서를 유지하는 Map이 아니라, accessOrder 옵션과 removeEldestEntry()를 통해 LRU 캐시를 편하게 구현할 수 있는 자료구조라는 점이 인상 깊었다.
앞으로는 문제를 풀 때 단순히 정답을 맞히는 데 그치지 않고, 어떤 자료구조가 어떤 상황에서 적합한지를 함께 고민하는 습관을 가져야겠다는 생각이 들었다.