[이진탐색][Java][BOJ] #11663. 선분 위의 점

#이진탐색  #silver3

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

 

🌷 문제 설명

✏️ 백준 연습문제: 선분 위의 점 
일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

⌨️ 입력
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

🖨️ 출력
입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

입출력 예

입력	출력
5 5 1 3 10 20 30 1 10 20 60 3 30 2 15 4 8	3 2 4 2 0

 

💡해결 포인트

1. 이진 탐색은 "정렬된" 배열을 대상으로 한다 Arrays.sort(배열명);

 

🌷 내 코드

어제부터 이진 탐색을 풀다 보니 대충 어떻게 풀지 감이 왔던 것 같다. 범위를 생각하는게 조금 헷갈려서 계속 손으로 짚어가며 풀었다. 🤦🏻‍♀️

import java.io.*;
import java.util.*;

public class BOJ_11663 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("example.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄 입력
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]); // 점 개수
        int M = Integer.parseInt(firstLine[1]); // 선분 개수

        // N개 좌표 입력
        int[] numbers = new int[N];
        String [] thirdLine = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(thirdLine[i]);
        }

        // 배열 정렬
        Arrays.sort(numbers);

        // M개 선분의 쌍 입력
        for (int i = 0; i < M; i++) {
          String[] secondLine = br.readLine().split(" ");
          int target1 = Integer.parseInt(secondLine[0]);
          int target2 = Integer.parseInt(secondLine[1]);

          // target1 index
          int target1Idx = 0;
          int target2Idx = 0;

          // target 1 이진탐색
          int left = 0;
          int right = N - 1;

          while (left <= right) {
              int mid = (left + right) / 2;

              if (numbers[mid] < target1) {
                  left = mid + 1;
              } else {
                  right = mid - 1;
              }
              target1Idx = left;
          }

          // target 2 이진탐색
          int left2 = 0;
          int right2 = N - 1;

          while (left2 <= right2) {
              int mid = (left2 + right2) / 2;

              if (numbers[mid] > target2) {
                  right2 = mid - 1;
              } else {
                  left2 = mid + 1;
              }
              target2Idx = left2;
          }

          System.out.println(target2Idx - target1Idx);
        }


    }
}

 

🌷 코멘트

한 번에 성공한건 첨이라 좀 감격(물론 그 전에 VS코드로 다 찍어 봄.. 근데 예전에도 그건 다 했는데 항상 채점을 돌리면 틀리는 포인트들이 있었는데 이번 문제는 그냥 다 돌아갔다. 그런데 채점 시간이 엄청 오래 걸렸다. 시간 초과 날까봐 엄청 조마조마 했음 나 자야돼ㅠ)

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview