알고리즘 풀이 · 중급

BST 연습: 닫힌 구간의 중복 키 보고서

··설명 약 6분·작성: 해비·블로그 소개

읽기 전에 알아두면 좋아요

아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.

개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.

과정 위치와 선택 복습 안내

과정 위치: 트리·그래프와 최단거리 · 문제

과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.

JavaScript로 문법·실행 복습하기 (선택)

개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.

BST 구간 보고서 문제에서는 중복 키를 포함한 트리의 어떤 키를 대상으로 하나요?

중복 키를 포함한 트리에서 닫힌 구간에 해당하는 키의 보고서를 만드는 문제입니다. 이진 탐색 트리·구간·중복의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.

적용 조건·범위: 입력은 엄격한 BST이며 공유 노드나 사이클이 없습니다. 정답 함수는 트리 전체의 유효성 검사를 다시 하지 않습니다. 표준 출력은 조건을 만족하는 숫자 배열이고 양쪽 경계와 같은 키도 포함합니다. 출력 개수가 커질 수 있으므로 count를 생략하거나 1로 추측해서 처리하지 않습니다.

본문 근거: Princeton Algorithms — Binary Search Trees

독립 창작 문제

이 문제의 상황·입출력 계약·예시는 이 글을 위해 직접 구성했습니다. 공식 문제를 번역하거나 복제한 지문이 아닙니다. 구현 개념은 JavaScript 이진 탐색 트리 구현: 중복 키와 세 가지 삭제 처리에서 먼저 확인할 수 있습니다.

이미 만들어진 이진 탐색 트리와 low, high가 주어집니다. low ≤ key ≤ high인 키를 중복 횟수 count만큼 오름차순으로 출력하세요. low가 high보다 크면 빈 배열을 반환합니다. 트리를 새로 구축하거나 변경할 필요는 없습니다.

각 노드의 왼쪽 부분 트리에는 더 작은 키, 오른쪽에는 더 큰 키만 존재합니다. 중복 키는 별도 노드로 나뉘지 않고 해당 노드의 count에 합쳐져 있습니다. 단순 이진 트리를 BST라고 가정하면 가지치기가 유효하지 않으므로 이 조건은 입력 계약의 핵심입니다.

입력·출력과 제약

표준 입력은 {root,low,high} JSON 객체입니다. root는 null 또는 {key,count,left,right} 노드입니다. key, low, high는 안전 정수이고 count는 필수 필드인 1~100의 정수입니다. 없는 자식은 null 또는 필드 생략입니다. 서로 다른 노드 수 U는 0~10000, count 합 N은 100000 이하, 최대 깊이는 200입니다.

입력은 엄격한 BST이며 공유 노드나 사이클이 없습니다. 정답 함수는 트리 전체의 유효성 검사를 다시 하지 않습니다. 표준 출력은 조건을 만족하는 숫자 배열이고 양쪽 경계와 같은 키도 포함합니다. 출력 개수가 커질 수 있으므로 count를 생략하거나 1로 추측해서 처리하지 않습니다.

입력 예시

{"root":{"key":12,"count":1,"left":{"key":7,"count":2,"left":null,"right":null},"right":{"key":18,"count":1,"left":{"key":14,"count":3,"left":null,"right":null},"right":null}},"low":7,"high":14}

출력 예시

[7,7,12,14,14,14]

실행 방법

Node.js CommonJS 환경에서 정답의 전체 코드를 bst-problem.cjs로 저장합니다. 입력 예시를 UTF-8 input.json 파일로 저장한 뒤 Windows PowerShell에서는 아래 명령을 실행하세요. 내장 node:fs 외에 다른 파일이나 패키지가 필요하지 않습니다.

Get-Content -Raw -Encoding UTF8 ./input.json | node ./bst-problem.cjs

macOS·Linux의 Bash에서는 아래 입력 리다이렉션을 사용할 수 있습니다. 이 < 문법은 PowerShell 명령이 아닙니다.

node ./bst-problem.cjs < input.json

힌트

현재 키가 low보다 작으면 왼쪽 전체도 작습니다. 반대로 중위 순회에서 꺼낸 키가 high를 넘으면 그 뒤에 나올 값은 전부 범위 밖입니다. 중위 순서를 유지하는 스택과 이 두 가지 생략 조건을 결합하세요.

직접 풀어보기

먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.

0 / 6,000바이트

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다. Tab은 다음 항목으로 이동합니다. 입력 영역 오른쪽 아래를 끌어 높이를 조절할 수 있습니다.

비밀키·개인정보는 입력하지 마세요. 코드는 이 페이지에만 유지됩니다.

해답·해설 보기
JavaScript 해답
'use strict';
function checkKey(key) {
    if (! Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}
function rangeValues(root, low, high) {
    checkKey(low);
    checkKey(high);
    const result = [];
    if (low > high) return result;
    const stack = [];
    let current = root;
    while (current != null || stack.length > 0) {
        while (current != null) {
            if (current.key < low) {
                current = current.right;
            } else {
                stack.push(current);
                current = current.left;
            }
        }
        if (stack.length === 0) break;
        current = stack.pop();
        if (current.key > high) break;
        for (let copy = 0; copy < current.count; copy += 1) {
            result.push(current.key);
        }
        current = current.right;
    }
    return result;
}
function solve( {
    root, low, high
}) {
    return rangeValues(root, low, high);
}

원문 JSON 객체를 파싱한 객체 input을 solve(input)에 전달하고 배열을 반환합니다. 표준 입출력은 포함하지 않습니다.

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

'use strict';

function checkKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}

function rangeValues(root, low, high) {
  checkKey(low);
  checkKey(high);
  const result = [];
  if (low > high) return result;
  const stack = [];
  let current = root;
  while (current != null || stack.length > 0) {
    while (current != null) {
      if (current.key < low) {
        current = current.right;
      } else {
        stack.push(current);
        current = current.left;
      }
    }
    if (stack.length === 0) break;
    current = stack.pop();
    if (current.key > high) break;
    for (let copy = 0; copy < current.count; copy += 1) {
      result.push(current.key);
    }
    current = current.right;
  }
  return result;
}


function solve({ root, low, high }) {
  return rangeValues(root, low, high);
}

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');
}

정답 해설: 순서가 생략을 정당화합니다

내부 반복에서 key < low인 노드는 스택에 저장하지 않고 오른쪽으로 넘어갑니다. 그 노드의 왼쪽까지 방문할 필요가 없기 때문입니다. 나머지는 스택에 쌓고 왼쪽으로 내려가 아직 출력하지 않은 작은 키를 먼저 처리합니다.

스택에서 꺼낸 키는 low 이상입니다. 그 키가 high를 넘으면 이후 중위 방문도 더 큰 키뿐이라 break로 전체 반복을 끝낼 수 있습니다. 범위 안이면 count만큼 결과에 추가하고 오른쪽 부분 트리로 이동합니다. 입력의 연결이나 count를 고치지 않는 읽기 전용 연산입니다.

예시 단계 판정 출력
루트 12 보류, 왼쪽 7 7은 low와 같음 7,7
스택의 12 처리 범위 안 7,7,12
오른쪽 18 보류, 왼쪽 14 14는 high와 같음 7,7,12,14,14,14
18 처리 시도 high 초과, 종료 변화 없음

예시에서는 왼쪽 키 7의 count가 2이고 키 14의 count가 3입니다. 같은 숫자를 여러 번 출력하는 것은 중복 방문 오류가 아니라 문제에서 요구한 확장입니다. low=high=14라면 14 세 개만 출력하고 low=15,high=14라면 탐색 없이 빈 결과입니다.

복잡도

h는 높이, k는 실제 출력 개수입니다. 유효한 BST에서 범위 안 노드와 두 경계로 가는 경로만 방문하므로 시간은 O(h+k+1), 최악 O(U+k)입니다. 보조 스택은 O(h+1), 결과는 O(k)입니다. 표준 입력 JSON 트리까지 포함한 전체 프로그램 공간은 O(U+k)이며, 트리 균형은 보장하지 않으므로 h를 무조건 log U로 바꾸면 안 됩니다.

이 문제는 완성된 트리를 받으므로 삽입으로 구축하는 비용은 없습니다. values 배열을 BST에 하나씩 넣는 별도 입력 설계를 택하면 정렬된 입력에서 구축만 O(U²)이 될 수 있습니다. 입력 형식이 달라지면 같은 범위 함수라도 프로그램 전체 복잡도가 달라집니다.

직접 확인할 경계

풀이 직접 실행

본문 풀이에 예제 입력을 넣고, 입력을 바꿔 계산 결과를 비교합니다.

예제 크게 보기 (새 탭)

빈 root, low > high, 모든 키보다 낮거나 높은 범위, 한 키만 포함하는 범위, 중복 횟수가 큰 노드, 편향 트리를 확인하세요. 테스트에서는 BST에 넣은 원래 다중집합을 filter 후 sort한 결과와 비교하면 가지치기 구현과 독립적으로 정답을 확인할 수 있습니다.

함께 연습하고 확인할 자료

Delete Node in a BST: BST 노드 삭제를 연습하는 외부 문제입니다. 이 글의 count 중복 정책과 달리 공식 입력의 키 조건을 따르세요.

관련 개념 참고: Princeton Algorithms — Binary Search Trees 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.

이 문제를 푼 뒤 확인하기

범위 양 끝과 같은 키가 여러 번 들어올 때 중복 횟수와 출력 순서를 확인해 보세요.

본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.

글 소개·학습 준비·전체 목차
이진 탐색 트리의 핵심 구조를 표현한 개념 표지
구조의 특징을 표현한 개념 이미지입니다. 정확한 동작은 아래 코드와 추적 표를 함께 확인하세요.

핵심 요약

중복 횟수를 가진 BST에서 닫힌 구간의 키만 오름차순으로 출력합니다. 모든 노드를 수집해 정렬하는 대신 BST의 순서로 불가능한 가지를 제외하는 독립 창작 문제입니다.

이 글이 도움이 되었나요?

조회 중

이어서 공부하기

체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 층별 방문 순서와 최솟값 추출을 추적하고, 다익스트라의 비음수 조건과 오래된 후보를 설명하세요.

다음 추천 · 자료구조 개념: JavaScript 최소 힙 구현: 우선순위 큐의 push·pop과 비교 함수

같은 주제에서 다음 개념과 예제로 이해를 넓힙니다.

권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.

원래 과정 목록 순서 (선택)

읽음 기록

읽음 — / 전체 58개 · 필수 58개

읽음 기록 설정

읽음 기록은 이 브라우저에만 저장됩니다.

이 글을 쓴 해비

웹사이트를 제작·운영하고, 개인 서비스와 자동화·AI 도구를 만듭니다. 직접 만들며 배운 내용과 문제 해결 과정을 BlogFlow에 기록합니다.

새 글 받아보기

RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.

RSS 피드 구독하기

댓글 남기기