여러 정렬 목록에서 k번째 작은 수
자바스크립트 코딩테스트 문제로 k-way-merge 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
오름차순으로 정렬된 정수 목록 여러 개가 주어질 때, 전체 값을 하나로 모았다고 가정했을 때 k번째로 작은 수를 반환하는 solution 함수를 작성하세요.
존재하지 않는 순서라면 null을 반환합니다.
제한사항
lists는 정수 배열을 원소로 가지는 배열입니다.- 각 내부 배열은 오름차순으로 정렬되어 있습니다.
- 내부 배열의 길이는 0 이상 100,000 이하입니다.
- 전체 원소 수의 합은 200,000 이하입니다.
- 원소는
-1000000000이상1000000000이하의 정수입니다. k는 1 이상1000000000이하의 정수입니다.- 전체 원소 수가
k보다 작으면null을 반환합니다.
예시
- 입력:
lists = [[-5, 1, 8], [-3, 4], [2, 6, 9]],k = 5→ 출력:4 - 입력:
lists = [[1, 1, 3], [1, 2, 2], [5]],k = 4→ 출력:2 - 입력:
lists = [[], [2, 3, 7], [], [4]],k = 3→ 출력:4 - 입력:
lists = [[10, 20], [30], []],k = 5→ 출력:null
힌트
- 모든 값을 한 번에 합쳐 정렬하면 쉽지만, 이미 각 목록이 정렬되어 있다는 점을 더 활용할 수 있습니다.
- 각 목록의 현재 가장 작은 후보만 비교해도 다음으로 작은 값을 고를 수 있습니다.
- 가장 작은 값을 빠르게 꺼내고 다음 후보를 다시 넣을 자료구조를 떠올려 보세요.
해설
이 문제는 여러 개의 정렬된 리스트를 동시에 합치는 k-way merge 감각을 익히는 문제입니다.
가장 단순한 방법은 모든 원소를 하나의 배열에 모아 정렬한 뒤 k - 1번째 값을 꺼내는 것입니다.
하지만 이 방법은 이미 각 리스트가 정렬되어 있다는 정보를 충분히 활용하지 못합니다.
더 좋은 방법은 최소 힙(min-heap)을 사용하는 것입니다.
- 각 리스트의 첫 번째 원소만 힙에 넣습니다.
- 힙 원소에는
값,리스트 번호,리스트 안의 인덱스를 함께 저장합니다.
- 힙 원소에는
- 힙에서 가장 작은 값을 하나 꺼냅니다.
- 방금 꺼낸 값이 전체에서 몇 번째인지 세고, 그 순서가
k라면 바로 반환합니다. - 꺼낸 값이 어떤 리스트의
idx번째 원소였다면, 그 리스트의idx + 1번째 원소를 힙에 넣습니다. - 힙이 빌 때까지 반복합니다.
예를 들어 [[1, 4, 10], [2, 3], [5, 8]]라면 처음 힙에는 1, 2, 5만 들어갑니다.
가장 작은 1을 꺼낸 뒤 같은 리스트의 다음 값 4를 넣고, 다시 가장 작은 2를 꺼내는 식으로 진행하면 전체 정렬 결과를 앞에서부터 하나씩 만든 것과 같습니다.
핵심은 각 리스트에서 아직 사용하지 않은 가장 앞 원소만 후보가 될 수 있다는 점입니다. 그래서 모든 원소를 다 정렬하지 않아도, 힙 크기를 리스트 수 수준으로 유지하면서 필요한 순서까지 효율적으로 탐색할 수 있습니다.
이 방식의 시간 복잡도는 힙 연산 기준으로 대략 O(k log m) 또는 전체를 끝까지 보면 O(T log m)입니다.
m: 리스트 개수T: 전체 원소 수
즉, 여러 정렬 리스트를 다룰 때 자주 쓰이는 최소 힙 활용법을 연습하기에 좋은 문제입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.