๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 30์ผ์ฐจ TIL - Find Right Interval

HOONSSACยท2024๋…„ 8์›” 20์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
30/41
post-thumbnail
post-custom-banner

โณ๋ฌธ์ œ

You are given an array of intervals, where intervals[i] = [starti_i, endi_i] and each starti_i is unique.

The right interval for an interval i is an interval j such that startj_j >= endi_i and startj_j is minimized. Note that i may equal j.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

๐Ÿ“ƒ์ž…์ถœ๋ ฅ ์˜ˆ

์ž…์ถœ๋ ฅ ์˜ˆ #1

InputOutput
intervals = [[1,2]][-1]

There is only one interval in the collection, so it outputs -1.

์ž…์ถœ๋ ฅ ์˜ˆ #2

InputOutput
intervals = [[3,4],[2,3],[1,2]][-1,0,1]

There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start0_0 = 3 is the smallest start that is >= end1_1 = 3. The right interval for [1,2] is [2,3] since start1_1 = 2 is the smallest start that is >= end2_2 = 2.

์ž…์ถœ๋ ฅ ์˜ˆ #3

InputOutput
intervals = [[1,4],[2,3],[3,4]][-1,2,-1]

There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2_2 = 3 is the smallest start that is >= end1_1 = 3.

๐Ÿšจ์ œํ•œ ์‚ฌํ•ญ

  • 1 <= intervals.length <= 2 * 104
  • intervals[i].length == 2
  • -106^6 <= starti_i <= endi_i <= 106`
  • The start point of each interval is unique.

โœ๏ธํ’€์ด

๐Ÿค”๋ฌธ์ œ์˜ ๋ชฉํ‘œ

์ด ๋ฌธ์ œ๋Š” ์‹œ์ž‘์ ๊ณผ ๋์ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ตฌ๊ฐ„ ์ค‘์—์„œ, ๊ฐ ๊ตฌ๊ฐ„์˜ ๋์ ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์‹œ์ž‘์ ์„ ๊ฐ€์ง„ ๊ตฌ๊ฐ„์„ ์ฐพ๋Š” ๊ฒƒ์ด๋‹ค. ๋‹จ, ๋งŒ์•ฝ ๊ทธ๋Ÿฐ ๊ตฌ๊ฐ„์ด ์—†๋‹ค๋ฉด -1์„ ๋ฐ˜ํ™˜ํ•ด์•ผ ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๊ตฌ๊ฐ„ ๋ฐฐ์—ด์ด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž

intervals = [[1, 2], [2, 3], [0, 1]]

์ด ๋ฐฐ์—ด์• ์„œ ๊ฐ ๊ตฌ๊ฐ„์„ ์‚ดํŽด๋ณด๋ฉด

1. ์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ [1, 2]

๋์ ์ด 2์ด๊ธฐ ๋•Œ๋ฌธ์—, ์‹œ์ž‘์ ์ด 2 ์ด์ƒ์ธ ๊ตฌ๊ฐ„์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค.
์—ฌ๊ธฐ์„œ๋Š” ๋‘ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ [2, 3]์ด ํ•ด๋‹น๋œ๋‹ค.
๋”ฐ๋ผ์„œ ์ธ๋ฑ์Šค 1์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

2. ๋‘ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ [2, 3]

๋์ ์ด 3์ด๊ธฐ ๋•Œ๋ฌธ์—, ์‹œ์ž‘์ ์ด 3 ์ด์ƒ์ธ ๊ตฌ๊ฐ„์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค.
ํ•˜์ง€๋งŒ ์ฃผ์–ด์ง„ ๊ตฌ๊ฐ„ ์ค‘์—์„œ๋Š” ๊ทธ๋Ÿฐ ๊ตฌ๊ฐ„์ด ์—†๋‹ค.
๋”ฐ๋ผ์„œ -1์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

3. ์„ธ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ [0, 1]

๋์ ์ด 1์ด๊ธฐ ๋•Œ๋ฌธ์—, ์‹œ์ž‘์ ์ด 1 ์ด์ƒ์ธ ๊ตฌ๊ฐ„์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค.
์—ฌ๊ธฐ์„œ๋Š” ์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ [1, 2]๊ฐ€ ํ•ด๋‹น๋œ๋‹ค.
๋”ฐ๋ผ์„œ ์ธ๋ฑ์Šค 0์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

์ตœ์ข… ๊ฒฐ๊ณผ

์ด ๋ชจ๋“  ๊ฒƒ์„ ์ข…ํ•ฉํ•˜๋ฉด, ๊ฐ ๊ตฌ๊ฐ„์— ๋Œ€ํ•œ ๊ฒฐ๊ณผ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • ์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ : 1
  • ๋‘ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ : -1
  • ์„ธ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ : 0

๋”ฐ๋ผ์„œ ์ตœ์ข…์ ์œผ๋กœ ๋ฐ˜ํ™˜๋˜๋Š” ๋ฐฐ์—ด์€ [1, -1, 0]์ด ๋œ๋‹ค.

๐Ÿค”์ ‘๊ทผ ๋ฐฉ๋ฒ•

  • ๊ฐ ๊ตฌ๊ฐ„์˜ ๋์ ์— ๋Œ€ํ•ด, ๊ทธ ๋์ ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์‹œ์ž‘์ ์„ ๊ฐ€์ง„ ๊ตฌ๊ฐ„์„ ์ฐพ๊ธฐ ์œ„ํ•ด ์ด์ง„ ํƒ์ƒ‰์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ๋” ํšจ์œจ์ ์ด๋‹ค.
  • ์ด์ง„ ํƒ์ƒ‰์„ ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฐฐ์—ด์ด ์ •๋ ฌ๋˜์–ด ์žˆ์–ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ๊ฐ ๊ตฌ๊ฐ„์˜ ์‹œ์ž‘์ ๊ณผ ๋์ ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ์„ ํ•ด์•ผ ํ•œ๋‹ค.
  • ์ด์ง„ ํƒ์ƒ‰์„ ํ†ตํ•ด ์ฐพ์€ ์ธ๋ฑ์Šฌ๋ฅด ๊ฒฐ๊ณผ ๋ฐฐ์—ด์— ์ €์žฅํ•˜๊ณ , ํ•ด๋‹น ๊ตฌ๊ฐ„์ด ์—†๋‹ค๋ฉด -1์„ ์ €์žฅํ•œ๋‹ค.

์ด์ง„ ํƒ์ƒ‰์— ๋Œ€ํ•œ ๊ฐœ๋…์€ ๋”ฐ๋กœ ์ฐพ์•„์„œ ์ •๋ฆฌ๋ฅผ ํ•ด ๋ณด์•˜๋‹ค.

๐Ÿ‘พ์ตœ์ข… ์ฝ”๋“œ

// intervals ์˜ˆ์‹œ : [[3,4], [2,3], [1,2]]

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] answer = new int[intervals.length];
        HashMap<Integer, Integer> startIndexMap = new HashMap<>();

        // ์‹œ์ž‘์ ๊ณผ ์ธ๋ฑ์Šค๋ฅผ ๋งคํ•‘ํ•˜์—ฌ ์ €์žฅ
        for (int i = 0; i < intervals.length; i++) {
            startIndexMap.put(intervals[i][0], i);
        }

        // startIndexMap
        // Key -> Value
        // 3 -> 0
        // 2 -> 1
        // 1 -> 2

        // ์‹œ์ž‘์  ๋ฐฐ์—ด์„ ์ •๋ ฌ
        int[][] sortedIntervals = new int[intervals.length][2];
        for (int i = 0; i < intervals.length; i++) {
            sortedIntervals[i] = intervals[i];
        }
        Arrays.sort(sortedIntervals, (a, b) -> Integer.compare(a[0], b[0]));

        // sortedIntervals
        // [[1,2], [2,3], [3,4]]

        // ๊ฐ ๊ตฌ๊ฐ„์˜ ๋์ ์— ๋Œ€ํ•ด ์ด์ง„ ํƒ์ƒ‰
        for (int i = 0; i < intervals.length; i++) {
            int end = intervals[i][1];
            int index = binarySearch(sortedIntervals, end);
            if (index == -1) {
                answer[i] = -1;
            }
            else {
                answer[i] = startIndexMap.get(sortedIntervals[index][0]);
            }
        }

        return answer;                      
    }

    // ์ด์ง„ ํƒ์ƒ‰
    public int binarySearch(int[][] intervals, int target) {
        int left = 0;
        int right = intervals.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] >= target) {
                result = mid; // ๊ฐ€๋Šฅํ•œ ์ธ๋ฑ์Šค ์ €์žฅ
                right = mid - 1; // ๋” ์ž‘์€ ์ธ๋ฑ์Šค๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ์™ผ์ชฝ์œผ๋กœ ์ด๋™
            }
            else {
                left = mid + 1; // ๋” ํฐ ์ธ๋ฑ์Šค๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ด๋™
            }
        }
        
        return result;
    }
}
  1. startIndexMap์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฐ ์‹œ์ž‘์ ๊ณผ ๊ทธ์— ํ•ด๋‹นํ•˜๋Š” ์ธ๋ฑ์Šค๋ฅผ ์ €์žฅํ•œ๋‹ค.
  2. sortedIntervals ๋ฐฐ์—ด์„ ์‹œ์ž‘์  ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
  3. ๊ฐ ๊ตฌ๊ฐ„์˜ ๋์ ์— ๋Œ€ํ•ด ์ด์ง„ ํƒ์ƒ‰์„ ์ˆ˜ํ–‰ํ•˜์—ฌ, ๊ทธ ๋์ ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์‹œ์ž‘์ ์„ ๊ฐ€์ง„ ๊ตฌ๊ฐ„์˜ ์ธ๋ฑ์Šค๋ฅผ ์ฐพ๋Š”๋‹ค
  4. ์ฐพ์€ ์ธ๋ฑ์Šค๋ฅผ ๊ฒฐ๊ณผ ๋ฐฐ์—ด์— ์ €์žฅํ•œ๋‹ค. ๋งŒ์•ฝ ํ•ด๋‹น ๊ตฌ๊ฐ„์ด ์—†๋‹ค๋ฉด -1์„ ์ €์žฅํ•œ๋‹ค.

๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰
post-custom-banner

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 20์ผ

๋‚ด์šฉ์ด ์•Œ์ฐจ๊ณ  ๊น”๋”ํ•œ TIL ์ž˜ ๋ณด๊ณ  ๊ฐ‘๋‹ˆ๋‹ท..!

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ