코딩테스트/알고리즘 문제풀이

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

2024. 8. 20. 14:14
목차
  1. 📜 문제 내용
  2. 🤔 과정
  3. ✨ 최초 제출 답안 - 🆖 테스트케이스 오답
  4. ✍️ 재제출 답안 - 🙆‍♂️ 통과
  5. 🔗 문제 링크
728x90
반응형

 

 

📜 문제 내용

 

🤔 과정

  • [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 (링크) 

 

728x90
반응형
저작자표시 (새창열림)
  1. 📜 문제 내용
  2. 🤔 과정
  3. ✨ 최초 제출 답안 - 🆖 테스트케이스 오답
  4. ✍️ 재제출 답안 - 🙆‍♂️ 통과
  5. 🔗 문제 링크
'코딩테스트/알고리즘 문제풀이' 카테고리의 다른 글
  • [99클럽 코테 스터디 32일차 TIL] 무인도 여행 - Java [자바][프로그래머스]
  • [99클럽 코테 스터디 31일차 TIL] 점프 점프 - Java [자바][백준]
  • [99클럽 코테 스터디 29일차 TIL] Longest Increasing Subsequence - Java [자바][LeetCode]
  • [99클럽 코테 스터디 28일차 TIL] 괄호 회전하기 - Java [자바][프로그래머스]
bonkri
bonkri
Swimming through the sea of ​​information
bonkri
Bon_chive
bonkri
전체
오늘
어제
Bonkri's GitHub
  • 분류 전체보기
    • 일상 기록
    • SSAFY
      • TENsion UP 10기!
      • SSAFYcial
    • 프로그래밍 언어
      • Java
    • IT 자격증
    • 코딩테스트
      • TIL
      • 유형별 개념
      • 알고리즘 문제풀이
반응형
250x250

인기 글

최근 글

최근 댓글

hELLO · Designed By 정상우.
bonkri
[99클럽 코테 스터디 30일차 TIL] Find Right Interval - Java [자바][LeetCode]
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.