99클럽 코테 스터디 30일차 TIL + 이분탐색

오늘의 문제 - 이분탐색

LeetCode - 436. Find Right Interval

https://leetcode.com/problems/find-right-interval/

---

풀이 및 접근 방식

먼저 문제 이해에 시간이 걸렸던 것 같다.

문제의 핵심은 각 구간(interval)의 끝 지점 이후에 시작하는 가장 가까운 구간(interval)의 인덱스를 찾는 것이다.

 

시작점만 모아놓은 리스트에서 이분탐색을 사용해 현재 구간의 끝지점보다 큰 시작점 중 최소인 시작점을 찾아야겠다고 생각했다.

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        
        s_list = [(interval[0], idx) for idx, interval in enumerate(intervals)]
        
        ans_list = []
        s_list.sort()
        
        for interval in intervals:
            ans = -1
            start = 0
            end = len(s_list)-1
            
            while start <= end:
                mid = (start+end)//2
                
                if s_list[mid][0] < interval[1]:
                    start = mid + 1
                else:
                    end = mid - 1
                    ans = s_list[mid][1]
                    
            ans_list.append(ans)
        
        return ans_list

풀이

1. s_list 생성 및 정렬
   각 구간의 시작점과 시작점의 인덱스를 튜플로 만들고, 이를 요소로 하는 s_list를 생성한다. 이후, s_list를 크기순으로 정렬한다.
2. 오른쪽 구간 탐색 - 이분탐색
   각 구간을 순회하며 s_list 중 현재 구간의 끝지점(interval[1])보다 크면서 최소인 시작점을 찾기 위해 이분탐색을 수행한다.
   - 시작점(s_list[mid][0])이 현재 구간의 끝지점보다 작으면 start를 mid+1로 설정하여 오른쪽 구간(더 큰 구간)을 탐색한다.
   - 그렇지 않다면, end를 mid-1로 설정하여 왼쪽 구간을 탐색한다. 이때는 끝지점보다 큰 것을 만족하면서 최소인 시작점일 수 있으므로, ans에 시작점의 인덱스를 저장한다.
   - 이분탐색이 종료되면 ans(각 구간의 결과값)을 ans_list에 추가한다.
3. ans_list를 반환한다.

시간 복잡도

• s_list 생성: 구간의 개수를 n이라고 하면, 이 부분은 O(n)이다.
• s_list 정렬: 정렬의 시간 복잡도는 O(n log n)이다.
• 오른쪽 구간 탐색: 각 구간에 대해 이진 탐색을 수행하므로 O(n log n)이다.

따라서, 전체 알고리즘의 시간 복잡도는 O(n log n)이다.

---

회고

와와 30일차 30일차~~~~