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

 

 

📜 문제 내용

 

🤔 과정

• [startI, endI] 가 Intervals 배열 안에 들어있고, endI보다 크거나 같은 가장 작은 startJ 값을 찾는 문제다. 
• 주어진 endI보다 크거나 같은 첫 번째 위치를 찾는 것이므로 하한값을 찾아야한다. 
• 1차원 정수형 배열 ans에는 default 값으로 -1를 배치한다. 
• hashMap에 ( Key, Value ) = ( startJ, Index ) 를 맵핑하여 put 한다. 
• hashMap에 있는 Key(startJ)들을 오름차순으로 정렬한 ArrayList 형태의 keySet을 생성한다. 
• 이분탐색을 통해 하한값을 찾고, 조건에 맞게 처리 

 

✨ 최초 제출 답안 - 🆖 테스트케이스 오답

class Solution {
      public int[] findRightInterval(int[][] intervals) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = intervals.length;
        int[] ans = new int[len];
        Arrays.fill(ans,-1);

        for (int i = 0; i < len; i++) {
            map.put(intervals[i][0], i);
        }

        for (int i = 0; i < len; i++) {
            int endI = intervals[i][1];
            if(ans[i] == -1 && map.containsKey(endI) && map.get(endI) != i){
                ans[i] = map.get(endI);
            }
        }

        return ans;
    }
}

 

 

• 일단 의식의 흐름대로 쭉 작성해서 제출했더니 테케 20개 중 15개만 맞았다. 당연한 결과였는데, 하한값을 찾지 않고, endI와 startJ가 같으면 넣는 방식으로 코드를 짰기 때문이다. 
• 그래서 endI가 정렬된 keySet을 이분탐색하면서 하한값을 찾게 만들었다.  

 

✍️ 재제출 답안 - 🙆‍♂️ 통과

class Solution {
    private List<Integer> keySet;

    public int[] findRightInterval(int[][] intervals) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = intervals.length;
        int[] ans = new int[len];
        Arrays.fill(ans, -1);  // 모든 값을 -1로 초기화함

        // Key : startJ , Value : intervals의 index
        for (int i = 0; i < len; i++) {
            map.put(intervals[i][0], i);
        }

        // keySet에는 startJ 값들을 정렬
        keySet = new ArrayList<>(map.keySet());
        Collections.sort(keySet);

        // 각 intervals의 endI 값에 대해 처리 및 순회
        for (int i = 0; i < len; i++) {
            int endI = intervals[i][1];

            // endI 값보다 크거나 같은 startJ 값을 가진 keySet에서의 하한값 위치를 찾는다
            int pos = findLowerBound(endI, 0, keySet.size() - 1);

            // 찾은 위치가 keySet 범위 내에 있고 그 위치의 값이 endI보다 크거나 같은 경우 
            // ans 배열에 map에서 해당 시작 값(key)에 대응하는 인덱스(value)를 저장
            // 없으면 -1 이 그대로 들어가있다. 
            if (pos < keySet.size() && keySet.get(pos) >= endI) {
                ans[i] = map.get(keySet.get(pos));
            }
        }
        return ans;
    }

    // 하한값을 찾는 이분탐색 메서드 
    private int findLowerBound(int num, int start, int end) {
        while (start < end) {
            int mid = (start + end) / 2;
            
            if (keySet.get(mid) < num) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        
        return start;
    }
}

 

 

🔗 문제 링크

• LeetCode - Find Right Interval (링크)