[LeetCode] 436. Find Right Interval # Binary Search

문제 링크

1. 문제 설명

 이중 배열 intervals가 주어진다. intervals의 요소 interval은 [start, end]로 구성되어있다. 반환해야할 answer의 i번째 요소는 현재의 end 값이 또 다른 interval의 start 값보다 작거나 같을 때, 최소값의 start를 가진 interval의 인덱스이다. 조건을 만족하는 start 값이 없다면 -1이 answer의 i번째 요소로 들어간다.

 

2.  제한 사항

• 1 <= intervals.length <= 2 * 10^4
• intervals[i].length == 2
• -10^6 <= start[i] < end[i] <= 10^6
• 각  interval의 start 값은 고유하다

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이(시간 초과) - Python

 문제의 조건을 그대로 구현했다. 결과는 시.간.초.과. 🤧 효율적으로 푸는 아이디어가 안 떠오른다..

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # 조건을 만족하는 intervals 중 최소의 start를 가진 interval이 right interval이므로 start 기준으로 오름차순으로 sort
        sorted_intervals = sorted(intervals)
        answer = [-1] * len(intervals)

        for i, i_val in enumerate(intervals): # O(n)
            for j, s_val in enumerate(sorted_intervals): # O(n)
                if i_val[1] <= s_val[0]:
                    answer[i] = intervals.index(s_val)
                    break
        
        return answer

 

 

5. 두 번째 풀이 - Python

 오늘도 클로드에게 물어본다.. 이 문제의 키워드는 이진탐색이었다. sorted_intervals에 start를 기준으로 (start, end, i) 튜플을 정렬한 리스트를 할당한다. 여기서 시간복잡도 O(nlogn)이 소요된다.

 

 리스트 컴프리헨션으로 starts에 sorted_intervals의 모든 start들을 넣은 리스트를 할당하고, 기존 intervals를 순회하면서 bisect_left 메소드를 사용해 모든 end들에 대해서 해당 end가 starts에 들어갈 수 있는 가장 왼쪽 인덱스를 반환한다. 이 과정의 시간복잡도는 O(log n)이다.

 

 반환된 인덱스가 starts의 개수보다 작으면 현재의 end 값보다 크거나 같은 start값이 있음을 의미하므로 answer에 해당 인덱스의 intervals에서의 인덱스 값을 넣어주고, 인덱스가 starts의 개수보다 크면 조건을 만족시키는 start값이 없음을 의미하기 때문에 -1을 넣어주면 된다. 

 

 최종 시간복잡도는 O(nlogn)이다. 첫 번째 풀이의 시간복잡도인 O(n^2)보다 O(n / log n)배 개선되었다.  

from bisect import bisect_left

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # intervals의 각 원소에 원래 인덱스를 포함시켜 저장
        sorted_intervals = sorted((start, end, i) for i, (start, end) in enumerate(intervals)) # O(nlogn)
        
        starts = [i[0] for i in sorted_intervals]
        answer = []
        
        for i, val in enumerate(intervals):
            # 이진 탐색을 사용해 end보다 큰 최소의 start를 찾음
            idx = bisect_left(starts, val[1]) # O(logn)
            if idx < len(starts):
                answer.append(sorted_intervals[idx][2])
            else:
                answer.append(-1)
        
        return answer

 

 

6. 세 번째 풀이 - Java

 Java에서는 이진 탐색을 직접 구현해야한다. 구현 방법에는 재귀와 while문을 사용한 반복구조가 있는데 재귀보다는 반복이 더 효율적이라고 한다. 그 이유는 재귀는 호출 시마다 새로운 스택 프레임이 생성되기 때문이다. 즉, 재귀를 사용할 때 입력의 크기가 매우 큰 경우 스택 오버플로우의 위험이 있다. 

 

 아래는 두 번째 풀이를 자바로 옮긴 코드다. 별거 아니자나..? 너무 재밌잖아. (세뇌)

import java.util.*;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        
        // intervals의 각 원소에 원래 인덱스를 포함시켜 저장
        int[][] sortedIntervals = new int[n][3];
        for (int i = 0; i < n; i++) {
            sortedIntervals[i] = new int[]{intervals[i][0], intervals[i][1], i};
        }
        
        // start를 기준으로 정렬
        Arrays.sort(sortedIntervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        int[] starts = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = sortedIntervals[i][0];
        }
        
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int idx = binarySearch(starts, end);
            if (idx < n) {
                answer[i] = sortedIntervals[idx][2];
            } else {
                answer[i] = -1;
            }
        }
        
        return answer;
    }
    
    // 이진 탐색 함수
    private int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

 

 

7. 다짐

 밑 빠진 독에 물 붓는 느낌을 너무 불쾌해하지 말자.. 당연히 겪는 과정이다. 지나가자

 

 

8. 새로 알게된 점

•  자바에는 정렬된 리스트를 반환하는 sorted(list) 함수가 없다. 정렬 방식에는 크게 삽입 시 정렬("sorting on insertion")과 요청 시 정렬("sorting on demand")이 있는데, sorted(list)는 삽입 시 정렬에 해당하고, 삽입 시 정렬은 "삽입 순서를 유지해야 하는" List 인터페이스의 명세를 위반하기 때문이다.
• 또, 자바는 명시적 작업을 선호하는 경향이 있어, 정렬과 같은 고비용 작업에 대한 암시적 수행을 피한다고 한다. 단, TreeSet이나 TreeMap 등 Java에서 제공하는 최적화된 컬렉션 사용은 허용된다. 자바에서는 일반적으로 리스트 정렬을 위해 java7 이하에서는 Collections.sort(list)를 사용하고, java8 이후부터는 list.sort(Comparator)를 사용한다. 이런 명시적 방식을 사용함으로써 개발자가 정렬 시점을 제어하도록 한다.
  • "요청 시 정렬"의 종류
    • 제자리 정렬
      • Collections.sort(list);
      • list.sort(Comparator);
     
    • 리스트 → 스트림 생성 → 정렬 → 새로운 리스트로 수집
      • List<Integer> numbers = new ArrayList<>(); 
        1. List<Integer> sortedList = numbers.stream().sorted().collect(Collectors.toList()); 
        2. TreeSet<Integer> sortedSet = numbers.stream().collect(Collectors.toCollection(() -> new TreeSet<>()));

참고:
https://www.baeldung.com/java-sorted-list