TypeScript 이진 탐색 연습: 숫자 카드 존재 여부 확인

직접 풀어볼 문제

서로 다른 정수가 적힌 카드 N개와 확인할 숫자 M개가 주어집니다. 확인할 숫자가 카드에 있으면 1, 없으면 0을 순서대로 출력하세요. 입력은 N, 카드 N개, M, 확인할 숫자 M개 순서이며 공백과 줄바꿈으로 구분합니다.

• 1 ≤ N, M ≤ 100,000
• 각 정수는 -10,000,000 이상 10,000,000 이하
• 카드는 서로 다른 정수이며, 확인할 숫자는 반복될 수 있음

5
-7 2 9 15 21
6
9 0 -7 21 22 9

예상 출력

1 0 1 1 0 1

먼저 includes로 각 숫자를 확인하는 방법과, 정렬된 배열에서 범위를 절반씩 줄이는 방법의 비용을 비교해 보세요.

한 번 정렬하고 여러 번 찾는 이유

질의마다 카드 전체를 확인하면 최악의 경우 N×M번 수준의 비교가 필요합니다. 카드를 정렬해 두면 중간값과 목표값의 크기를 비교해 남은 구간 절반을 제외할 수 있습니다. 정렬 자체에는 비용이 들지만 질의가 많을수록 반복 탐색 비용을 줄일 수 있습니다.

Set도 존재 여부 확인에 적합합니다. 이 글에서는 정렬된 데이터의 탐색 범위를 관리하는 연습을 위해 이진 탐색을 사용합니다. 이진 탐색이 모든 상황에서 Set보다 빠르다는 뜻은 아닙니다.

9를 찾는 과정과 0이 없음을 확인하는 과정

left와 right는 현재 후보 구간의 양끝 인덱스입니다. 비교한 mid는 다음 후보에서 제외하므로 mid+1 또는 mid-1로 갱신합니다. mid를 다시 포함시키면 구간이 줄지 않아 반복문이 끝나지 않을 수 있습니다.

TypeScript 풀이

export function binarySearch(sorted: readonly number[], target: number): boolean {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (sorted[mid] === target) return true;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}
export function solve(input: string): string {
  const tokens = input.trim().split(/s+/).map(Number);
  let index = 0;
  const n = tokens[index++];
  const cards = tokens.slice(index, index + n);
  index += n;
  const m = tokens[index++];
  const queries = tokens.slice(index, index + m);
  cards.sort((a, b) => a - b);
  return queries.map((target) => binarySearch(cards, target) ? "1" : "0").join(" ");
}

위 코드를 solution.ts로 저장합니다. solve는 입력 문자열을 받아 출력 문자열을 반환하므로 파일 입출력과 분리해 검증할 수 있습니다. 아래의 main.ts는 표준 입력을 읽고 결과를 출력하는 실행 진입점입니다.

import { readFileSync } from "node:fs";
import { solve } from "./solution.js";
console.log(solve(readFileSync(0, "utf8")));

TypeScript와 Node 타입이 설치된 환경에서 아래처럼 컴파일합니다. input.txt에는 앞의 예제 입력을 넣습니다.

npx tsc solution.ts main.ts --target ES2022 --module NodeNext --moduleResolution NodeNext --outDir dist
node dist/main.js < input.txt

정수 정렬에는 숫자 비교 함수가 필요합니다. 또한 입력을 공백 전체로 나누는 정규식은 /s+/입니다. 역슬래시가 빠진 /s+/와 다르므로 복사 후 확인하세요.

시간·공간 비용

통상적인 비교 정렬 비용을 O(N log N)으로 보고, 질의마다 O(log N)이 걸리므로 전체는 O(N log N + M log N)입니다. 이 표기는 정렬 구현에 대한 일반적인 분석 가정이며 JavaScript 표준이 특정 정렬 알고리즘을 지정한다는 뜻은 아닙니다.

반복형 binarySearch 자체는 추가 공간 O(1)입니다. 그러나 전체 프로그램은 입력 토큰, 카드·질의 배열과 출력 배열을 보관하므로 정렬 내부 작업 공간을 제외해도 O(N+M)이 필요합니다. 탐색 함수 공간과 프로그램 전체 공간을 구분해야 합니다.

경계값과 반례 확인

입력 카드 순서가 뒤섞인 경우, 첫 값과 마지막 값, 없는 값, 같은 숫자를 반복해서 찾는 경우를 확인합니다. 이진 탐색 함수에 직접 전달하는 배열은 반드시 정렬되어 있어야 합니다.

학습용 입력은 조건을 만족한다고 가정합니다. 일반 사용자 입력을 받는 서비스에 재사용한다면 토큰 수, 숫자 형식, 범위 검사도 추가해야 합니다.

이어서 읽을 글

• JavaScript 코딩테스트 학습 순서
• TypeScript 배열에서 타입 추론하기