프로그래머스 | 카카오 [1차] 캐시

🔗 문제 링크

📝 문제 개요

• 입력: 도시 이름이 담긴 배열 cities, 캐시 크기 cacheSize
• 규칙: 대소문자 구분 없이 동일 도시로 간주
• 캐시 처리 비용:
  • Hit: 1
  • Miss: 5
• 출력: 총 처리 시간

🎯 해결 목표

LRU (Least Recently Used) 알고리즘을 사용하여 캐시 정책에 따라 도시 이름을 넣고 뺄 때 처리 비용을 정확히 계산해야 함

---

📚 사전 지식: LRU (Least Recently Used)

LRU 알고리즘은 가장 오래 전에 사용된 항목을 우선 제거하는 캐시 교체 정책입니다.

• 가장 최근에 접근한 항목은 캐시 내에서 뒤쪽
• 오래된 항목은 앞쪽에 위치하도록 유지
• 캐시에 데이터가 없으면 miss → 삽입
• 이미 있다면 hit → 기존 항목을 제거하고 다시 넣어서 가장 최신으로 이동

---

🐛 초기 시도: arr

function solution(cacheSize, cities) {
  const citiestoLower = cities.map(e => e.toLowerCase());
  const arr = [];
  let answer = 0;

  for (let i = 0; i < cities.length; i++) {
    answer = arr.includes(citiestoLower[i]) ? answer + 1 : answer + 5;
    arr.push(citiestoLower[i]);
    if (arr.length > cacheSize) arr.shift();
  }

  return answer;
}

❌ 문제점

• includes()로 hit 판별 후 중복 제거 없이 push
• LRU 순서가 갱신되지 않음 → 캐시에 같은 값이 중복 존재할 수 있음 (예: 서울, 판교, 서울)
• 그 결과 shift()로 엉뚱한 항목이 제거됨 → LRU 정책 위반

---

💻 solution 1: Set

function solution(cacheSize, cities) {
  if (cacheSize === 0) return cities.length * 5;

  const cache = new Set();
  let answer = 0;

  for (const city of cities) {
    const key = city.toLowerCase();

    if (cache.has(key)) {
      cache.delete(key); // 갱신
      cache.add(key);
      answer += 1;
    } else {
      if (cache.size >= cacheSize) {
        const oldest = cache.values().next().value; // 첫 값을 감지하는 정석적인 방법
        cache.delete(oldest);
      }
      cache.add(key);
      answer += 5;
    }
  }

  return answer;
}

삽입 순서가 유지되면서 arr의 includes보다 빠르고, 값만 관리하기 때문에 가장 적합함

---

💻 solution 2: Map

function solution(cacheSize, cities) {
  if (cacheSize === 0) return cities.length * 5;

  const cache = new Map();
  let cost = 0;

  for (const city of cities) {
    const key = city.toLowerCase();

    if (cache.has(key)) {
      cache.delete(key);
      cache.set(key, true);
      cost += 1;
    } else {
      if (cache.size >= cacheSize) {
        const oldest = cache.keys().next().value; // key로 탐색
        cache.delete(oldest);
      }
      cache.set(key, true);
      cost += 5;
    }
  }

  return cost;
}

✅ Map을 사용한 이유

• 실제 캐시 시스템은 보통 key → value 구조로 동작함 (ex. URL → 데이터)
• Map은 삽입 순서를 유지하면서도 키 기반 접근과 삭제가 효율적임
• 실무에서는 값뿐 아니라 메타데이터(예: timestamp, value 등)를 함께 저장하는 경우가 많아 Map이 더 일반적임

---

✅ 결론 요약

항목	Set 방식	Map 방식
코드 길이	짧고 간단	약간 더 길음
효율성	매우 좋음	거의 동일 (LRU 동작에 적합)
현실성	단일 값일 경우 적합	실무에서 더 자주 쓰임 (key-value 구조)
확장성	제한적	확장 유리 (value, timestamp 등 저장 가능)

학습 목적엔 Set이 간단하고 효율적이지만,
실제 캐시처럼 동작하는 구조를 이해하려면 Map을 활용한 구현을 익히는 것이 더 현실적이다.