코딩테스트 JS LRU 캐시: 지도 타일 재사용 기록

Node.js 24 CommonJS용 전체 풀이입니다. lru-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 .input.json | node .lru-problem.cjs

macOS / Linux:
node lru-problem.cjs < input.json

class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 0 || capacity > 1_000_000) {
      throw new RangeError('용량은 0~1,000,000 정수여야 합니다.');
    }
    this.capacity = capacity;
    this.map = new Map();
    this.head = { prev: null, next: null };
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  detach(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
  }
  attachFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.detach(node);
    this.attachFront(node);
    return node.value;
  }
  put(key, value) {
    if (value === undefined) throw new TypeError('undefined는 누락 표시로 예약합니다.');
    if (this.capacity === 0) return;
    const old = this.map.get(key);
    if (old) {
      old.value = value;
      this.detach(old);
      this.attachFront(old);
      return;
    }
    if (this.map.size === this.capacity) {
      const victim = this.tail.prev;
      this.detach(victim);
      this.map.delete(victim.key);
    }
    const node = { key, value, prev: null, next: null };
    this.map.set(key, node);
    this.attachFront(node);
  }
  keys() {
    const result = [];
    for (let node = this.head.next; node !== this.tail; node = node.next) result.push(node.key);
    return result;
  }
}

function solve({ capacity, requests }) {
  const cache = new LRUCache(capacity), hits = [];
  for (const key of requests) {
    const hit = cache.get(key) !== undefined;
    hits.push(hit);
    if (!hit) cache.put(key, true);
  }
  return { hits, keys: cache.keys() };
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

북, 남 요청은 모두 누락입니다. 세 번째 북은 적중해 북이 MRU가 됩니다. 동이 들어오면 남이 퇴출됩니다. 다음 남은 누락이라 북을 퇴출하고 마지막 남은 적중입니다. solve는 payload에 true를 저장하므로 get의 undefined와 확실히 구분됩니다. 최종 keys 호출은 전체 요청 처리가 끝난 뒤 한 번만 수행합니다.

head와 tail은 실제 데이터를 담지 않는 센티널입니다. head.next가 MRU, tail.prev가 LRU입니다. 비었을 때 head.next===tail, tail.prev===head입니다. 실제 노드마다 node.prev.next===node, node.next.prev===node가 유지되어야 어느 위치든 같은 두 줄로 제거할 수 있습니다.

Map의 각 값은 리스트에 정확히 한 번 등장하는 같은 노드 객체입니다. 리스트에서만 퇴출하면 Map에 오래된 항목이 남고, Map에서만 지우면 리스트 길이가 용량을 넘습니다. 따라서 퇴출은 detach와 map.delete를 같이 수행합니다.

길이가 제한된 키와 해시 Map 기대 모델에서 q개 요청은 기대 상환 O(q), 마지막 keys는 O(c), 보유 구조 O(c+1), 출력 O(q+c)입니다. c는 capacity와 실제 서로 다른 요청 수 중 작은 값입니다. Map 최악 상수 시간은 보장하지 않습니다.

표본과 경계를 직접 확인하려면 다음 코드를 lru-check.cjs로 저장하고 같은 폴더에서 node lru-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./lru-problem.cjs');

assert.deepEqual(
  solve({
  "capacity": 2,
  "requests": [
    "북",
    "남",
    "북",
    "동",
    "남",
    "남"
  ]
}),
  {"hits":[false,false,true,false,false,true],"keys":["남","동"]},
);
assert.deepEqual(
  solve({
  "capacity": 0,
  "requests": [
    "a",
    "a"
  ]
}),
  {"hits":[false,false],"keys":[]},
);