JavaScript 원형 덱 연습: 최근 기록 창과 되돌리기

한 파일로 실행하는 전체 정답

'use strict';

class CircularDeque {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new RangeError('capacity must be a positive integer');
    }
    this.data = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.length = 0;
  }

  pushFront(value) {
    if (this.length === this.capacity) return false;
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.data[this.front] = value;
    this.length += 1;
    return true;
  }

  pushBack(value) {
    if (this.length === this.capacity) return false;
    const index = (this.front + this.length) % this.capacity;
    this.data[index] = value;
    this.length += 1;
    return true;
  }

  popFront() {
    if (this.length === 0) return { done: true };
    const value = this.data[this.front];
    this.data[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.length -= 1;
    return { done: false, value };
  }

  popBack() {
    if (this.length === 0) return { done: true };
    const index = (this.front + this.length - 1) % this.capacity;
    const value = this.data[index];
    this.data[index] = undefined;
    this.length -= 1;
    return { done: false, value };
  }

  toArray() {
    const result = [];
    for (let offset = 0; offset < this.length; offset += 1) {
      result.push(this.data[(this.front + offset) % this.capacity]);
    }
    return result;
  }
}

function solve({ capacity, events }) {
  const deque = new CircularDeque(capacity);
  const snapshots = [];
  for (const event of events) {
    if (event.type === 'add') {
      if (!deque.pushBack(event.value)) {
        deque.popFront();
        deque.pushBack(event.value);
      }
    } else if (event.type === 'undo') {
      deque.popBack();
    } else {
      throw new TypeError('unknown event type');
    }
    snapshots.push(deque.toArray());
  }
  return snapshots;
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: 자료구조와 정책을 분리합니다

CircularDeque는 가득 찬 삽입에 false만 돌려줍니다. solve는 이 실패를 기록 창의 퇴출 조건으로 해석해 앞의 한 항목을 제거합니다. 용량이 1 이상이므로 한 번 제거한 다음 재삽입은 반드시 성공합니다. 이 논리는 버퍼 정책이며 덱 메서드의 보편적인 동작은 아닙니다.

undo는 popBack의 반환값이 done:true여도 그대로 진행합니다. 빈 상태의 undo가 유효한 명령이기 때문입니다. 이벤트마다 toArray가 새 배열을 만들어 snapshots에 넣으므로 그 뒤 덱의 슬롯이 재사용되어도 지난 스냅숏은 바뀌지 않습니다. 이 문제의 값은 원시값으로 제한해 깊은 객체 복사 문제도 피합니다.

불변식은 이벤트 i개를 처리한 뒤 덱이 “지금 창에 남은 기록”만 순서대로 보관하고 길이는 capacity 이하라는 것입니다. add가 남길 수 있는 가장 오래된 기록만 하나 버리고 undo가 마지막 하나만 지우므로 각 분기가 이 조건을 유지합니다. 출력은 그 상태를 그대로 복사합니다.

복잡도

K는 capacity, Q는 이벤트 수, S는 모든 스냅숏 길이의 합입니다. 덱 갱신은 이벤트마다 O(1)이지만 출력 복사는 O(S)이므로 총 시간은 O(Q+K+S), 최악 O(K+QK)입니다. 덱만 보면 O(K) 공간이지만 입력 JSON과 결과까지 보관하는 전체 프로그램은 O(K+Q+S+C) 공간입니다. C는 입력 문자열 총길이이며 최악의 스냅숏 원소 수는 QK입니다.

직접 확인할 경계

capacity=1에서 연속 add, 첫 이벤트 undo, events=[], 같은 값 두 번, null 저장, 물리 배열 끝을 여러 번 지나는 이벤트를 확인하세요. 최종 창만 맞는지 비교하지 말고 모든 중간 스냅숏을 배열 기반 기준 구현과 비교해야 undo 이전의 출력 복사 오류를 찾을 수 있습니다.