코딩테스트 연습장

1 / 8

비유로 이해하기

은행 창구 앞에 늘어선 줄을 떠올려 보세요. 새로 온 사람은 맨 뒤에 서고, 창구는 맨 앞 사람부터 부릅니다. 먼저 온 사람이 먼저 나가는 이 규칙이 전부입니다. 그런데 처리 방식은 두 가지입니다. 맨 앞 사람이 빠질 때마다 뒤 사람이 전부 한 발씩 앞으로 걸어오는 방식과, 사람은 그대로 서 있고 "지금 차례" 번호표만 다음으로 넘기는 방식입니다. 결과는 같지만 뒤에 100명이 서 있다면 수고는 100배 차이입니다.

큐는 뒤로 들어와 앞으로 나가는 FIFO(First-In First-Out, 선입선출) 자료구조입니다.

들어올 때: 줄 맨 뒤 → enqueue
나갈 때: 줄 맨 앞 → dequeue
빠른 방식: 줄을 당기지 말고 "지금 차례" 표시만 앞으로 옮긴다

번호표를 뽑은 손님 10, 20, 30이 차례로 들어오고 두 명이 처리되는 과정을, "번호표만 옮기는" 방식으로 따라가 봅니다. head가 지금 차례를 가리키는 표시입니다.

단계	동작	배열 상태	head	꺼낸 값
1	enqueue(10)	`[10]`	0	—
2	enqueue(20)	`[10, 20]`	0	—
3	enqueue(30)	`[10, 20, 30]`	0	—
4	dequeue()	`[10, 20, 30]`	1	10
5	dequeue()	`[10, 20, 30]`	2	20

배열은 한 번도 움직이지 않았고 head만 0 → 1 → 2로 전진했습니다. 남은 원소가 있는지는 head < queue.length로 판단합니다. 지금은 2 < 3이므로 30이 아직 남아 있습니다.

같은 일을 shift()로 했다면 4단계에서 20과 30이, 5단계에서 30이 한 칸씩 실제로 이동했을 것입니다. 원소가 10만 개라면 그 이동이 그대로 시간 초과가 됩니다.

배열과 head 표시를 함께 준비합니다 — 이 둘이 한 세트로 큐입니다.

const queue: number[] = [];
let head = 0;

enqueue는 뒤에 붙이기입니다 — 배열 끝 추가는 O(1)입니다.

queue.push(10);
queue.push(20);

dequeue는 head 위치를 읽고 한 칸 전진시킵니다 — 배열은 건드리지 않습니다.

const cur = queue[head++]; // 배열은 그대로 두고 포인터만 전진 — O(1)

남은 것이 있는지는 head와 길이를 비교합니다.

while (head < queue.length) { /* ... */ }

전체 코드 — "각 작업을 한 번에 2개씩만 처리하고, 남으면 줄 뒤로 보내기":

function solution(tasks: number[]): number[] {
  // 1단계: 배열 + head 표시
  const queue: number[] = [...tasks.keys()]; // 작업 번호
  const remain = [...tasks];
  let head = 0;
  const done: number[] = [];
  // 4단계: 남은 것이 있는 동안
  while (head < queue.length) {
    const id = queue[head++];          // 3단계: dequeue
    remain[id] -= 2;                   // 한 번에 2개씩 처리
    if (remain[id] > 0) queue.push(id); // 2단계: 남으면 다시 enqueue
    else done.push(id);                // 끝났으면 완료 순서에 기록
  }
  return done;
}

"먼저 온 순서대로 처리한다", "대기열", "번호표", "줄을 선다" — 지문에 이런 말이 있으면 큐입니다.
BFS(너비 우선 탐색): 가까운 곳부터 층층이 퍼져나가는 탐색 — 큐가 곧 탐색 순서
시간 순 시뮬레이션: 레일 위의 로봇, 프린터 대기열, 은행 창구 — "먼저 온 순서대로 처리"가 규칙인 모든 것
최근 K개 유지: 슬라이딩 윈도우에서 오래된 것부터 버릴 때
"최소 몇 번 만에", "최단 거리", "동시에 퍼져나간다" — 가중치가 없는 최단 거리는 큐(BFS)의 영역입니다.

기본 연산과 비용은 다음과 같습니다.

연산	의미	비고
enqueue(x)	뒤에 x를 붙인다	O(1)
dequeue()	앞에서 꺼낸다	O(1)이어야 함
front()	앞을 꺼내지 않고 본다	O(1)

JS/TS에서의 함정: shift()는 O(N)

배열의 shift()는 모든 원소를 한 칸씩 당기므로 **O(N)**입니다. BFS처럼 dequeue가 수만 번 일어나면 전체가 O(N²)이 되어 시간 초과가 납니다. 코테에서는 head 인덱스 방식을 쓰세요.

// head 인덱스 큐 — dequeue O(1)
const queue: number[] = [];
let head = 0;
queue.push(1); queue.push(2);        // enqueue
while (head < queue.length) {
  const cur = queue[head++];         // dequeue — 배열은 그대로 두고 포인터만 전진
  // ...cur 처리
}

BFS 뼈대 — 격자에서 최단 거리

function bfs(grid: number[][], sr: number, sc: number): number[][] {
  const [n, m] = [grid.length, grid[0].length];
  const dist = Array.from({ length: n }, () => Array(m).fill(-1));
  const queue: [number, number][] = [[sr, sc]];
  let head = 0;
  dist[sr][sc] = 0;
  const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (let d = 0; d < 4; d++) {
      const nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
      if (grid[nr][nc] === 0 || dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;  // 큐에 넣을 때 거리 확정 — 중복 방문 차단
      queue.push([nr, nc]);
    }
  }
  return dist;
}

레벨(층) 단위 처리 — "몇 초 뒤에 전부 퍼지는가"류는 현재 큐 길이만큼만 끊어서 한 층으로 봅니다.

let time = 0;
while (head < queue.length) {
  let size = queue.length - head;   // 이번 층의 개수를 먼저 고정
  while (size-- > 0) { const cur = queue[head++]; /* 이웃을 push */ }
  time++;                            // 한 층이 끝날 때마다 1초
}

shift() 사용으로 시간 초과 — 위의 head 인덱스로 교체

while (queue.length) { const cur = queue.shift()!; }   // 잘못된 코드 — 매번 O(N)
while (head < queue.length) { const cur = queue[head++]; } // 고친 코드 — O(1)

BFS에서 방문 표시를 꺼낼 때 함 — 같은 칸이 큐에 여러 번 들어가 폭발합니다. 넣을 때 표시하세요

// 잘못된 코드
const [r, c] = queue[head++];
visited[r][c] = true;               // 이미 여러 번 들어온 뒤입니다
// 고친 코드
if (!visited[nr][nc]) { visited[nr][nc] = true; queue.push([nr, nc]); }

시뮬레이션에서 "이번 턴에 들어온 것"과 "기존 것"을 구분 안 함 — 레벨(층) 단위 BFS는 현재 큐 길이만큼만 끊어서 처리

while (head < queue.length) { ... }              // 잘못된 코드 — 층 경계가 사라짐
let size = queue.length - head; while (size-- > 0) { ... } // 고친 코드 — 이번 층만