728x90
https://leetcode.com/problems/find-right-interval/description/
[문제]
주어진 여러 개의 구간(intervals)에서 각 구간에 대해 "우측 구간"을 찾아야 합니다. "우측 구간"이란 현재 구간의 끝 지점(end) 이후에 시작되는 구간 중에서 시작 지점이 가장 작은 구간을 말합니다.
- intervals는 [start, end] 형태의 구간들이 들어있는 배열입니다.
- intervals[i]는 [start_i, end_i] 형태로, start_i와 end_i는 각각 구간의 시작과 끝을 의미합니다.
- 문제에서 주어진 각 start_i는 유일(unique)합니다.
- 각 구간 i에 대해 "우측 구간"의 인덱스를 반환하는 배열을 만들어야 합니다.
- 만약 "우측 구간"이 존재하지 않는다면, 해당 인덱스 위치에는 -1을 반환해야 합니다.
- 각 구간 i의 끝점 end_i에 대해 start_j >= end_i를 만족하는 구간 j 중에서 start_j가 가장 작은 구간을 찾습니다.
- 예를 들어, intervals = [[3,4],[2,3],[1,2]]일 때:
- [3,4]의 경우, 끝점이 4이므로 시작점이 4 이상인 구간이 없습니다. 따라서 -1을 반환합니다.
- [2,3]의 경우, 끝점이 3이고, 시작점이 3 이상인 구간 [3,4]가 있습니다. 이 구간의 인덱스는 0입니다.
- [1,2]의 경우, 끝점이 2이고, 시작점이 2 이상인 구간 [2,3]이 있습니다. 이 구간의 인덱스는 1입니다.
- 예제 1: intervals = [[1,2]]
- 이 경우, 구간이 하나뿐이므로 우측 구간이 존재하지 않으며, 결과는 [-1]입니다.
- 예제 2: intervals = [[3,4],[2,3],[1,2]]
- 결과는 [-1, 0, 1]입니다.
- 예제 3: intervals = [[1,4],[2,3],[3,4]]
- 결과는 [-1, 2, -1]입니다.
- 주어진 구간 배열에서 각 구간에 대해 해당 구간의 끝점 이후에 시작되는 구간을 찾아야 하며, 그런 구간이 없으면 -1을 반환합니다.
이 문제는 사실 이해하는 부분부터서 막혀서 풀지 못했습니다.
선택된 배열의 결국 마지막 요소 값 이상으로 시작(어떤 배열의 첫 번째 인덱스와 동일)하는 구간이 있다면 해당 값이 존재하는 '배열의 인덱스'를 정리하여 반환하고, 시작하는 배열이 없다면 -1을 반환하도록 구성해야하는 문제입니다.
먼저 각 배열을 data class 또는 Tripple 클래스로 (현재 인덱스, start(0), end(1)) 정리해줍니다.
이때, 어차피 시작점 비교를 모든 배열에 대해 비교해야하므로 정렬에 용이하게 start 기준으로 정렬해줍니다.
val indexedIntervals = intervals.mapIndexed { index, interval ->
Triple(index, interval[0], interval[1])
}.sortedBy { it.second }
결과 값을 담아줄 리스트를 기본 반환값 -1로 초기화하여 생성한 뒤,
코틀린에서 제공하는 이진 탐색 함수를 활용하여 '가장 작은 시작 지점이 end 이상'인 구간을 찾습니다.
for (interval in indexedIntervals) {
val (_, _, end) = interval
// 이진 탐색을 통해 가장 작은 시작 지점이 end 이상인 구간 찾기
val rightIntervalIndex = indexedIntervals.binarySearch { it.second.compareTo(end) }
val adjustedIndex = if (rightIntervalIndex < 0) -rightIntervalIndex - 1 else rightIntervalIndex
if (adjustedIndex < indexedIntervals.size) {
result[interval.first] = indexedIntervals[adjustedIndex].first
}
}
만약 해당 구간이 존재한다면, 결과 배열에 해당 구간의 원래 인덱스를 저장합니다.
그리고 각 구간에 대해 찾아낸 "우측 구간"의 인덱스를 결과 배열에 담아 반환합니다.
이분 탐색 자체 함수를 활용하는 방법도 코틀린에는 존재하나.. 일단 이분 탐색을 활용하기까지 문제를 이해하는 능력을 먼저 키워야겠네요;
728x90
