코딩테스트 JS 연결 리스트: 재생 대기 목록 관리

Node.js 24 CommonJS용 코드입니다. 전체를 linked-list-playlist-problem.cjs로 저장하고 예시 입력을 input.txt에 UTF-8로 저장합니다. 아래 명령은 셸에 맞게 하나를 골라 사용하세요.

PowerShell 7 (UTF-8 파이프):

Get-Content -Raw -Encoding UTF8 .\input.txt | node .\linked-list-playlist-problem.cjs

macOS / Linux Bash:

node linked-list-playlist-problem.cjs < input.txt

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  append(value) {
    const node = { value, next: null };
    if (this.tail) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length += 1;
  }
  removeFirst() {
    if (!this.head) {
      return { done: true };
    }
    const node = this.head;
    this.head = node.next;
    node.next = null;
    this.length -= 1;
    if (this.length === 0) {
      this.tail = null;
    }
    return { done: false, value: node.value };
  }
  find(value) {
    for (let node = this.head; node; node = node.next) {
      if (node.value === value) {
        return node;
      }
    }
    return null;
  }
  remove(value) {
    let previous = null;
    let current = this.head;
    while (current && current.value !== value) {
      previous = current;
      current = current.next;
    }
    if (!current) {
      return false;
    }
    if (previous) {
      previous.next = current.next;
    } else {
      this.head = current.next;
    }
    if (current === this.tail) {
      this.tail = previous;
    }
    current.next = null;
    this.length -= 1;
    return true;
  }
  toArray() {
    const values = [];
    for (let node = this.head; node; node = node.next) {
      values.push(node.value);
    }
    return values;
  }
}

function solve(input) {
  const text = input.trim();
  if (!text) {
    return '';
  }
  const lines = text.split(/\r?\n/);
  const count = Number(lines[0]);
  const list = new SinglyLinkedList();
  const output = [];
  for (let i = 1; i <= count; i++) {
    const [command, title] = lines[i].split(' ');
    if (command === 'ADD') {
      list.append(title);
    } else if (command === 'PLAY') {
      const result = list.removeFirst();
      output.push(result.done ? 'EMPTY' : result.value);
    } else if (command === 'LIST') {
      output.push(list.toArray().join(',') || 'EMPTY');
    }
  }
  return output.join('\n');
}

module.exports = { solve };

if (require.main === module) {
  const input = require('node:fs').readFileSync(0, 'utf8');
  process.stdout.write(solve(input));
}

명령과 상태 변화

왜 이 구현으로 맞는가

전체 정답에 SinglyLinkedList를 포함했습니다. append는 tail을 이미 알고 있어 바로 연결하고, removeFirst는 head를 다음 노드로 옮깁니다. 이 두 연산에 임의 인덱스 조회가 필요하지 않으므로 단방향 연결 리스트로 충분합니다. LIST가 필요할 때만 모든 노드를 순서대로 따라갑니다.

목록이 빈 상태의 불변식은 head===null, tail===null, length===0입니다. 한 노드를 추가하면 head와 tail이 같은 노드를 가리키며 tail.next는 null입니다. removeFirst로 마지막 노드를 없앨 때 tail을 그대로 두면 다음 append가 이미 제거한 노드 뒤에 연결되므로 tail도 초기화해야 합니다.

solve는 ADD에 대해서는 출력하지 않고 PLAY의 결과와 LIST의 스냅샷만 output에 넣습니다. LIST는 관찰일 뿐 목록을 제거하지 않습니다. 따라서 다음 PLAY는 LIST에 표시된 첫 곡을 그대로 반환해야 합니다. 중복 제목도 별개 노드라 하나를 재생해도 다음 같은 제목이 남을 수 있습니다.

가이드와 같은 클래스에는 find와 remove도 들어 있지만 이 문제의 solve는 append, removeFirst, toArray만 사용합니다. 노드 참조와 head·tail이 공개되어 있으므로 외부에서 next를 수정하지 않는 계약을 지킵니다. 노드를 직접 건드리지 않고 메서드로만 목록을 바꾸면 상태 추적이 단순해집니다.

시간·공간과 문자열 비용

append와 removeFirst는 노드 연산 기준 최악 O(1)이고 LIST는 현재 K개 노드를 방문한 뒤 제목을 결합합니다. 입력 문자 수 S, 출력 문자 수 R, 명령 수 Q로 쓰면 전체 시간은 O(S+Q+R)입니다. 반복 LIST의 출력 때문에 R이 Q에 비해 크게 늘 수 있어 단순 O(Q)라고 할 수 없습니다. 구조만 보면 O(K) 노드지만 입력 문자열·줄 배열·출력 누적과 반환 문자열을 포함한 전체 공간은 O(S+Q+R+K), K≤Q이므로 O(S+Q+R)입니다. 제목 복사·연결 비용도 문자 수에 포함했습니다.

표본을 직접 확인하는 코드

다음 코드를 linked-list-playlist-check.cjs로 저장한 뒤 node linked-list-playlist-check.cjs로 실행하세요. assert가 일치하면 출력 없이 종료하고, 결과가 다르면 예외가 발생합니다. 같은 폴더의 정답 파일을 가져오는 이 블록은 풀이 본체가 아니라 표본 확인용입니다.

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

const input = "8\nADD 봄\nADD 여름\nLIST\nPLAY\nADD 여름\nPLAY\nPLAY\nPLAY";
const expected = "봄,여름\n봄\n여름\n여름\nEMPTY";
assert.equal(solve(input), expected);
assert.equal(solve("1\nPLAY"), "EMPTY");
assert.equal(solve('0'), '');