[백준 | Java] 11663번 선분 위의 점

728x90

11663번 / 선분 위의 점

❓ 선분 위의 점

🏷️ 관련 주제 : binarySearch

문제

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

입력

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

출력

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

예제 입력 1

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

예제 출력 1

출처

문제를 만든 사람: baekjoon

알고리즘 분류

정렬
이분 탐색

💦 나의 시도

점의 개수 N, 선분의 개수 M을 입력 받음.
0 ~ (N - 1) 범위에서 반복문을 돌며 길이 N인 int형 배열 dots에 순서대로 점의 위치를 입력받아 넣음.
dots를 오름차순 정렬
0 ~ (M - 1) 범위에서 반복문을 돌며 선분의 시작점과 끝점을 입력 받음.
binarySearch() 메서드를 사용하여 dots 배열에 선분의 시작점과 끝점으로 이진 탐색 실행
- dots에 선분의 점이 존재하면 dots에서 해당 점과 일치하는 값의 인덱스를 반환
- dots에 선분의 시작점이나 끝점이 존재하지 않으면 {(선분의 점이 들어갈 위치 인덱스) + 1} * -1을 반환
시작점의 이진 탐색 결과를 idx0에 할당, 끝점의 이진 탐색 결과를 idx1에 할당
선분의 양 끝점이 dots에 존재하지 않는 경우, 경우에 따라 선분 위에 존재하는 점의 개수를 반환 혹은 idx0, idx1의 값을 조정하여 선분 위의 점 개수를 구하여 BufferedWriter에 쓰기
- idx0가 음수인 경우
  - idx0가 배열의 제일 끝에 들어가는 경우, 0을 BufferWriter에 쓰고(bw.write())
    반복문 처음으로 돌아감.
  - 그 외의 경우, idx0에 (idx0 + 1) * -1을 할당
    (선분의 시작점 바로 뒤에 위치한 점의 인덱스를 할당)
- idx1이 음수인 경우
  - idx1이 배열의 제일 끝에 들어가는 경우, (N - idx0)을 BufferWriter에 쓰고(bw.write())
    반복문 처음으로 돌아감.
  - 그 외의 경우, idx1에 (idx1 + 2) * -1을 할당
    (선분의 끝점 바로 앞에 위치한 점의 인덱스를 할당)
- 선분의 끝점이 dots[0] 보다 왼쪽에 있는 경우, 0을 BufferWriter에 쓰고(bw.write())
  반복문 처음으로 돌아감.
- 그 외의 경우, (idx1 - idx0 + 1) 값을 BufferWriter에 쓰기(bw.write())
BufferedWriter의 문자열 출력하기(bw.close())

💥 7번 부분에서 엄청나게 오답이 많이 나옴.

Arrays.binarySearch();의 결과값이 배열에 찾고자하는 값이 존재하는 경우와 그렇지 않은 경우 서로 다른데

이러한 각 경우에 따라 인덱스를 조정하여 선분 위의 점 개수 구하는 부분에서 값을 많이 조정해야 했다.

🎉드디어 성공!🎉

메모리 : 73460 KB
시간 : 680 ms

📑제출 기록 및 오답 원인

이진 탐색 부분에서 인덱스 조정하는 부분에서 코드를 정확하게 작성하지 않아 많이 틀렸다.

💯 해결 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main (String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 점의 개수
        int M = Integer.parseInt(st.nextToken());  // 선분의 개수
        st = new StringTokenizer(br.readLine());

        int[] dots = new int[N];

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

        Arrays.sort(dots);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int lineStart = Integer.parseInt(st.nextToken());
            int lineEnd = Integer.parseInt(st.nextToken());
            int idx0 = Arrays.binarySearch(dots, lineStart);

            if (idx0 < 0) {
                if (idx0 == N * -1 - 1) {
                    bw.write(0 + "\n");
                    continue;
                }

                idx0 = (idx0 + 1) * -1;
            }

            int idx1 = Arrays.binarySearch(dots, lineEnd);

            if (idx1 < 0) {
                if (idx1 == N * -1 - 1) {
                    bw.write((N - idx0) + "\n");
                    continue;
                }
                
                idx1 = (idx1 + 2) * -1;
            }

            if (idx1 < idx0 || (idx1 == 0 && dots[0] != lineEnd)) {
                bw.write(0 + "\n");
                continue;
            }

            bw.write((idx1 - idx0 + 1) + "\n");
        }

        bw.close();
    }
}

🏷️ 문제 풀면서 참고한 블로그