문제 설명
배열이 주어질 때, 특정 구간에서 K번째로 작은 수를 찾는 문제입니다.
정수 배열과 두 개의 정수 L과 R, 그리고 K가 주어질 때,
L부터 R까지의 구간에 해당하는 수들 중 K번째로 작은 수를 반환하는 알고리즘을 작성하세요.
입력 형식
- 첫 번째 줄에는 N (1 ≤ N ≤ 100,000)과 Q (1 ≤ Q ≤ 100,000)가 주어집니다.
- 두 번째 줄에는 N개의 정수 A₁, A₂, ..., Aₙ (-1,000,000,000 ≤ Aᵢ ≤ 1,000,000,000)이 주어집니다.
- 이어서 Q개의 쿼리가 주어지며, 각 쿼리는 L, R, K 형태입니다.
출력 형식
각 쿼리에 대해 K번째로 작은 수를 출력하세요.
각 출력은 새로운 줄에 하나씩 출력되어야 합니다.
예제
입력
5 3
1 5 2 6 3
2 4 3
1 5 2
2 5 1
출력
5
2
3
문제 해결 과정
이 문제는 기본적으로 구간 쿼리를 다루는 문제입니다.
여러 쿼리를 처리하면서, 매번 구간에서 K번째 수를 찾는 최적의 알고리즘을 고민해야 합니다.
1단계: 문제 분석
N개의 원소를 가진 배열이 주어지고, Q개의 쿼리가 주어질 때,
각 쿼리는 배열의 부분 배열에서 K번째 수를 찾아야 합니다.
배열의 구간을 매번 정렬하여 K번째 수를 찾으면 O(N * log(N))의 시간이 소요되므로
비효율적입니다. 쿼리 수가 많아지면 가능성이 낮습니다.
2단계: 해결 방법 설계
이 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있습니다.
– **훔쳐보기 알고리즘**: 구간의 수들을 정렬하여 K번째 수를 효율적으로 찾도록 합니다.
– **계수 정렬 또는 부분 배열 정렬**: 부분 배열을 먼저 정렬한 후 K번째 수를 찾는 방법.
3단계: 알고리즘 구현
func kthSmallest(arr: [Int], l: Int, r: Int, k: Int) -> Int {
var subArray = Array(arr[l...r]) // 부분 배열 생성
subArray.sort() // 정렬
return subArray[k - 1] // K번째 작은 수 반환
}
func solveProblem(arr: [Int], queries: [(Int, Int, Int)]) {
for query in queries {
let (l, r, k) = query
let answer = kthSmallest(arr: arr, l: l, r: r, k: k)
print(answer)
}
}
4단계: 시간 복잡도 분석
위의 알고리즘은 매 쿼리마다 O(N log N)의 시간이 소요되므로,
Q개의 쿼리를 처리하게 되면 최악의 경우 O(Q * N log N)의 시간 복잡도를 가집니다.
이는 매우 크므로, 이 문제를 더 효율적으로 해결할 필요가 있습니다.
효율적인 해결 방법: 세그먼트 트리 또는 펜윅 트리
효율적인 방법으로는 세그먼트 트리나 펜윅 트리를 활용하여 각각의 구간에서 K번째 수를
찾도록 할 수 있습니다. 그러나 이 부분은 다루지 않도록 하겠습니다.
5단계: 마무리
이렇게 K번째 수를 구하는 문제를 해결하는 과정을 살펴보았습니다.
각각의 쿼리마다 구간을 정렬하는 방식으로 접근했지만,
좀 더 효율적인 방법을 사용하면 더 빠른 쿼리 처리로 문제를 해결할 수 있습니다.
이는 다음 강좌에서 다루도록 하겠습니다.
결론
코딩 테스트 문제를 해결하는 과정에서 문제를 정확하게 이해하고
효율적인 알고리즘을 설계하는 것은 매우 중요합니다.
여러 방법을 시도해보고 자신만의 방법을 정립해 보세요.
다음 강좌에서는 데이터 구조의 활용 등 좀 더 심화된 내용을 다룰 예정입니다.
감사합니다!