코딩테스트 JS 큐: 상담 창구 대기열 명령 처리

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

PowerShell 7 (UTF-8 파이프):

Get-Content -Raw -Encoding UTF8 .\input.txt | node .\queue-helpdesk-problem.cjs

macOS / Linux Bash:

node queue-helpdesk-problem.cjs < input.txt

function createQueue() {
  let items = [];
  let head = 0;
  return {
    enqueue(value) {
      items.push(value);
    },
    dequeue() {
      if (head === items.length) {
        return { done: true };
      }
      const value = items[head];
      items[head] = undefined;
      head += 1;
      if (head === items.length) {
        items = [];
        head = 0;
      } else if (head >= 1024 && head * 2 >= items.length) {
        items = items.slice(head);
        head = 0;
      }
      return { done: false, value };
    },
    size() {
      return items.length - head;
    },
  };
}

function solve(input) {
  const text = input.trim();
  if (!text) {
    return '';
  }
  const lines = text.split(/\r?\n/);
  const count = Number(lines[0]);
  const queue = createQueue();
  const output = [];
  for (let i = 1; i <= count; i++) {
    const [command, name] = lines[i].split(' ');
    if (command === 'ARRIVE') {
      queue.enqueue(name);
    } else if (command === 'CALL') {
      const result = queue.dequeue();
      output.push(result.done ? 'EMPTY' : result.value);
    } else if (command === 'COUNT') {
      output.push(String(queue.size()));
    }
  }
  return output.join('\n');
}

module.exports = { solve };

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

명령과 상태 변화

왜 이 구현으로 맞는가

정답 파일은 createQueue 선언부터 solve, 표준 입력 처리까지 포함합니다. 다른 가이드 파일을 require하지 않습니다. Node 내장 fs만 표준 입력을 읽는 데 사용합니다. 유효 입력 계약을 가정하는 연습 풀이이며 잘못된 명령·누락 줄을 진단하는 파서는 아닙니다.

solve는 첫 줄의 명령 수를 읽고 정확히 그만큼 순회합니다. ARRIVE에는 반환할 결과가 없으므로 output에 넣지 않습니다. CALL은 dequeue의 done으로 빈 상태를 구분하고 COUNT는 size를 문자열로 바꿉니다. output.join("\n")은 결과 사이에만 줄바꿈을 넣어 Q=0일 때 빈 문자열을 반환합니다.

각 명령 직전 큐의 유효 구간에는 아직 호출하지 않은 방문만 도착 순으로 남아 있습니다. enqueue가 뒤에 추가하고 dequeue가 앞의 한 항목만 제거하므로 명령 처리 뒤에도 이 불변식은 유지됩니다. COUNT가 전체 items.length를 읽으면 이미 호출한 슬롯까지 세므로 반드시 size를 사용합니다.

head가 커지면 소비한 앞부분이 물리 배열에 남습니다. dequeue는 사용한 슬롯의 참조를 먼저 끊고, 충분히 많은 슬롯을 소비했을 때 남은 값만 복사합니다. 한 압축은 O(K)이지만 그 비용을 앞선 제거들에 나누면 큐 연산은 분할 상환 O(1)입니다.

시간·공간과 문자열 비용

큐에 남은 최대 항목 수를 K라 하면 큐 구조만의 공간은 O(K+1024)입니다. 그러나 이 프로그램은 전체 입력 문자열, 줄 배열, 출력 배열과 마지막 결합 문자열까지 메모리에 보관합니다. 입력 문자 수 S, 출력 문자 수 R, 명령 수 Q를 포함한 전체 추가 저장은 O(S+R+Q+K), K≤Q이므로 O(S+R+Q)입니다. 따라서 프로그램 전체 공간을 O(K)라고 쓰면 입력·출력을 빠뜨립니다. 문자열 처리까지 포함한 총시간은 통상적 동적 배열 모델에서 O(S+R+Q) 상환이며, 큐 연산만 따로 보면 O(Q) 상환입니다.

표본을 직접 확인하는 코드

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

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

const input = "7\nARRIVE 민수\nARRIVE 수지\nCALL\nARRIVE 준호\nCOUNT\nCALL\nCALL";
const expected = "민수\n2\n수지\n준호";
assert.equal(solve(input), expected);
assert.equal(solve("2\nCALL\nCOUNT"), "EMPTY\n0");
assert.equal(solve('0'), '');