[Algorithm] 99클럽 코테 스터디 3일차 TIL | 백준_선분 위의 점(11663번)

2025. 1. 15. 14:21·Algorithm

https://www.acmicpc.net/problem/11663

분명 이진 탐색 알고리즘인건 알겠는데..

그래서 어떻게 풀지 고민이 됐던 문제다.

 

우선 점의 좌표 배열을 오름차순으로 정렬하고

배열에서 선분의 시작점 이상인 첫번째 위치를 찾고

배열에서 선분의 끝점 이하인 첫번째 위치를 찾는다.

 

 그리고 이 위치를 찾기 위해 이분탐색을 활용한다.

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()); //시작점
            int b = Integer.parseInt(st.nextToken()); //끝점

            // 배열에서 a이상인 첫 번째 위치 반환
            int startIdx = lowerBound(arr, a);
            // 배열에서 b이하인 첫 번째 위치 반환
            int endIdx = upperBound(arr, b);
            sb.append(endIdx - startIdx).append("\n");
        }
        System.out.println(sb.toString());
    }
    public static int lowerBound(int[] arr, int a){
        int low = 0;
        int high = arr.length-1;

        while(low <= high){
            int mid = (low + high) / 2;
            if(arr[mid] >= a){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }

    public static int upperBound(int[] arr, int b){
        int low = 0;
        int high = arr.length-1;

        while(low <= high){
            int mid = (low + high) / 2;
            if(arr[mid] <= b){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return high+1;
    }
}

 

 

'Algorithm' 카테고리의 다른 글

[Algorithm] 99클럽 코테 스터디 5일차 TIL | 백준_두 용액(2470번)  (0) 2025.01.17
[Algorithm] 99클럽 코테 스터디 4일차 TIL | 백준_기타 레슨(2343번)  (10) 2025.01.16
[Algorithm] 99클럽 코테 스터디 2일차 TIL | 백준_랜선 자르기(1654번)  (0) 2025.01.14
[Algorithm] 99클럽 코테 스터디 1일차 TIL | 백준_암기왕(2776번)  (0) 2025.01.13
[Algorithm] 프로그래머스_모의고사(JAVA)  (1) 2024.12.14
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 99클럽 코테 스터디 5일차 TIL | 백준_두 용액(2470번)
  • [Algorithm] 99클럽 코테 스터디 4일차 TIL | 백준_기타 레슨(2343번)
  • [Algorithm] 99클럽 코테 스터디 2일차 TIL | 백준_랜선 자르기(1654번)
  • [Algorithm] 99클럽 코테 스터디 1일차 TIL | 백준_암기왕(2776번)
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (147)
      • Front-end (0)
      • Back-end (11)
        • Spring (1)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (80)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      99클럽
      개발자취업
      TypeScript
      티스토리챌린지
      항해99
      Til
      코딩테스트준비
      오블완
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 99클럽 코테 스터디 3일차 TIL | 백준_선분 위의 점(11663번)
    상단으로

    티스토리툴바