구간에서 K번째 작은 수 빠르게 찾기
자바스크립트 코딩테스트 문제로 persistent-segment-tree 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
정수 배열 nums와 여러 개의 질의 queries가 주어집니다. 각 질의는 [left, right, k] 형태이며, nums[left]부터 nums[right]까지의 부분 배열을 오름차순으로 정렬했을 때 k번째로 작은 값을 물어봅니다.
모든 질의의 답을 같은 순서의 배열로 반환하는 solution 함수를 작성하세요.
예를 들어 nums = [5, 1, 2, 2, 9]이고 질의가 [0, 4, 3]이면 전체 구간을 정렬한 결과는 [1, 2, 2, 5, 9]이므로 3번째 작은 값은 2입니다.
제한사항
nums의 길이는 1 이상 100,000 이하입니다.queries의 길이는 1 이상 100,000 이하입니다.nums[i]는 -1,000,000,000 이상 1,000,000,000 이하의 정수입니다.- 각 질의는
[left, right, k]형태입니다. 0 <= left <= right < nums.length입니다.1 <= k <= right - left + 1입니다.- 반환값은 각 질의의 k번째 작은 값을 담은 배열입니다.
예시
- 입력:
[5, 1, 2, 2, 9],[[0, 4, 3], [1, 3, 2], [2, 2, 1]]→ 출력:[2, 2, 2] - 입력:
[-3, 7, -3, 0, 5],[[0, 2, 1], [0, 4, 4], [3, 4, 2]]→ 출력:[-3, 5, 5] - 입력:
[10],[[0, 0, 1]]→ 출력:[10]
힌트
- 질의마다 구간을 잘라 정렬하면 최악의 경우 너무 느립니다.
- 배열의 값들을 먼저 좌표 압축하면, 값의 실제 크기 대신 정렬 순위로 빈도를 셀 수 있습니다.
0..right접두사 빈도에서0..left-1접두사 빈도를 빼면left..right구간의 값 빈도만 남습니다.
해설
이 문제는 구간 질의가 많기 때문에 매번 부분 배열을 정렬하는 방식으로는 통과하기 어렵습니다. 핵심은 각 접두사마다 “어떤 값이 몇 번 등장했는지”를 빠르게 비교할 수 있는 구조를 만드는 것입니다.
먼저 nums에 등장하는 서로 다른 값을 정렬해 좌표 압축합니다. 그러면 각 숫자는 정렬된 값 목록에서의 인덱스로 바뀌고, k번째 작은 값을 찾는 일은 압축 인덱스의 누적 빈도에서 k번째 위치를 찾는 일이 됩니다.
그다음 영속 세그먼트 트리를 사용합니다.
roots[0]은 아무 값도 넣지 않은 빈 버전입니다.i번째 숫자를 추가해roots[i + 1]을 만듭니다.- 새 버전은 이전 버전 전체를 복사하지 않고, 값이 추가되는 경로의 노드만 새로 만듭니다.
- 질의
[left, right, k]에서는roots[right + 1]과roots[left]를 비교합니다. - 두 버전의 왼쪽 자식 빈도 차이가
k이상이면 답은 왼쪽 절반에 있습니다. - 그렇지 않으면 그 빈도만큼
k를 줄이고 오른쪽 절반으로 이동합니다. - 리프에 도착하면 해당 압축 인덱스의 원래 값을 반환합니다.
이 방식은 전처리에 O(n log n), 각 질의에 O(log n)이 걸립니다. 중복 값은 같은 압축 인덱스의 빈도가 여러 번 증가하는 방식으로 자연스럽게 처리되고, 음수나 큰 값도 좌표 압축 덕분에 같은 구조로 다룰 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.