99클럽 코테 스터디 30일차 TIL - [LeetCode] Find Right Interval (Java)

📌 오늘의 학습 키워드

[LeetCode] Find Right Interval (Java)
https://leetcode.com/problems/find-right-interval/description/

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : int[][] intervals - [start, end]로 구성된 하나의 구간(Interval)을 나타냄
출력 : 각 구간에 대해 해당 구간의 끝점보다 크거나 같은 시작점을 가진 가장 작은 구간의 인덱스 반환. 없으면 -1 반환

가능한 시간복잡도

O(n log n)

알고리즘 선택

이진탐색

📌 코드 설계하기

1. TreeMap<Integer, Integer>를 사용하여 각 인터벌의 시작점을 키로, 해당 인터벌의 인덱스를 값으로 저장한다. TreeMap은 자동으로 키를 정렬하므로 이진 탐색을 쉽게 할 수 있다.
2. 각 인터벌에 대해 intervals[i][1] (인터벌의 끝점)보다 크거나 같은 최소 시작점을 찾기 위해 TreeMap의 ceilingKey 메서드를 사용한다. 이 메서드는 주어진 키보다 크거나 같은 최소의 키를 반환한다.
3. 만약 ceilingKey가 null을 반환한다면, 해당 인터벌에 대해 오른쪽 인터벌이 없다는 의미이므로 결과 배열에 -1을 저장한다. 그렇지 않으면, 해당 시작점에 대응하는 인덱스를 결과 배열에 저장한다.
4. 결과 배열을 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[] result = new int[n];
        TreeMap<Integer, Integer> map = new TreeMap<>();

        // Intervals의 시작점을 TreeMap에 저장, key는 시작점, value는 인덱스
        for (int i = 0; i < n; i++) {
            map.put(intervals[i][0], i);
        }

        // 각 interval에 대해 right interval 찾기
        for (int i = 0; i < n; i++) {
            Integer key = map.ceilingKey(intervals[i][1]);
            result[i] = key == null ? -1 : map.get(key);
        }

        return result;
    }
}