[Algorithm] 99클럽 코테 스터디 3일차 TIL BOJ 11663

문제

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

풀이

문제 분석

• 2일차에 풀었던 문제처럼 이분탐색으로 풀어야 한다는 것을 알 수 있었다
• 문제를 풀기위한 과정을 정리하면 다음과 같다

1. 입력받은 점들을 배열(point)에 저장하고 오름차순으로 정렬한다
2. 각각 주어지는 선분에 대하여 시작점과 끝점이 포함되는지를 검사하기 위해 이분탐색을 사용한다
  - 주어진 선분의 시작점(start)보다 크거나 같은 첫번째 점의 위치를 point 배열에서 찾는다(lower bound)
  - 주어진 선분의 끝점(end)보다 큰 첫번째 점의 위치를 point 배열에서 찾는다(upper bound)
3. upper_bound(end) - lower_bound(start)를 하면 정답을 구할 수 있다

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] token = br.readLine().split(" ");
        int N = Integer.parseInt(token[0]); // 점의 개수
        int M = Integer.parseInt(token[1]); // 선분의 개수
        long[] point = new long[N];
        String[] points = br.readLine().split(" ");
        for(int i = 0; i < N; i++) {
            point[i] = Long.parseLong(points[i]);
        }
        Arrays.sort(point);

        for(int i=0 ; i<M ; i++) {
            token = br.readLine().split(" ");
            int start = Integer.parseInt(token[0]); // 선분의 시작점
            int end = Integer.parseInt(token[1]); // 선분의 끝점
            bw.write(getCount(point, start, end) + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static String getCount(long[] point, int start, int end) {
        int startIdx = lowerBound(point, start);
        int endIdx = upperBound(point, end);
        int count = endIdx - startIdx;
        return String.valueOf(count);
    }

    private static int upperBound(long[] data, int target) {
        int begin = 0;
        int end = data.length;

        while(begin < end) {
            int mid = (begin + end) / 2;

            if(data[mid] <= target) {
                begin = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return end;
    }

    private static int lowerBound(long[] data, int target) {
        int begin = 0;
        int end = data.length;

        while(begin < end) {
            int mid = (begin + end) / 2;

            if(data[mid]>= target) {
                end = mid;
            }
            else {
                begin = mid + 1;
            }
        }
        return end;
    }
}

TIL

오늘 문제를 해결하는데 놓쳤던 부분은 이분탐색에서 중요한 정렬이었다
예시가 정렬된 점을 나열하고 있어 놓쳤던 것 같은데, 다음에 문제를 풀 때에는 놓치지 않아야 겠다고 생각했다
(정렬 한줄 추가하고 바로 통과했기 때문..)

또한 lower_bound와 upper_bound를 이용하여 개수를 셀 때에는 end-start+1이 아닌 end-start로 계산해야 하는 것도 깨달았다
개수를 셀 때 무조건 +1을 하는 습관보다 구하고자 하는 값에 대해 한번 더 고려해야겠다는 생각이 들었다

만약 다음과 같은 입력이 주어진다면,

5 1
1 2 3 4 5
4 6

정답은 2가 도출되어야 한다
이때 lower_bound(4) = 3, upper_bound(6) = 5가 도출된다
따라서 5-3을 했을 때 정답인 2가 출력되는 것을 확인할 수 있다