99클럽 코테 스터디 30일차 TIL , Find Right Interval

문제

풀이

입력으로 구간들이 주어지면

각 구간의 종점과 같거나 큰 시작점을 가지는 구간이 있으면 그 구간의 인덱스를 출력하면 된다.

조건을 만족하는 구간이 여러 개라면 가장 작은 인덱스를 반환하면 된다.

제출 1 - 정답

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] answer = new int[intervals.length];	//정답 배열
        Map<int[], Integer> map = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            answer[i] = -1;	//-1로 초기화
            map.put(intervals[i],i);	//각 구간 인덱스 넣음
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] i1, int[] i2) {
                return (i1[0] - i2[0]);	//고유값으로 정렬
            }
        });

        for(int[] interval : intervals){
            int start = interval[0];	//필요없긴 함
            int end = interval[1];	
            int lt = 0;
            int rt = intervals.length-1;
            while(lt <= rt){
                int mid = (lt + rt) / 2;
                if(intervals[mid][0] == end){
                    answer[map.get(interval)] = map.get(intervals[mid]);
                    break;
                }else if(intervals[mid][0] < end){
                    lt = mid+1;
                }else{	//end보다 클 경우
                    if(answer[map.get(interval)] == -1){	//아직 초기화 그대로면 넣어줌
                        answer[map.get(interval)] = map.get(intervals[mid]);
                    }else{	//값이 변해 있으면 비교 후 넣어줌
                        answer[map.get(interval)] = Math.min(map.get(intervals[mid]), answer[map.get(interval)]);
                    }
                    rt = mid-1;	//같은 경우를 제외 하면 큰 값중 인덱스가 작은 값으로 넣어줘야 하기 때문에 반복
                }
            }
        }

        return answer;
    }
}

 

각 구간 인덱스를 Map에 저장해 두고 start값이 고유 값이기 때문에 고윳값을 기준으로 이분탐색 하면서 end값 이상의 구간을 찾아준다.

TIL

• 이분탐색