[랜덤 마라톤] 선분 위의 점(11663)

1. 문제 풀이 아이디어

• 이진 검색을 사용하여 시작점 이상인 값 중 가장 작은 값과 끝점 이하인 값 중 가장 큰 값을 구하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());

        int[] p = new int[n];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        Arrays.sort(p);
        
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int s = Integer.parseInt(stringTokenizer.nextToken());
            int e = Integer.parseInt(stringTokenizer.nextToken());

            int startIdx = lowerBound(p, s);
            int endIdx = upperBound(p, e);

            stringBuilder.append(endIdx - startIdx + 1).append("\n");
        }
        
        System.out.print(stringBuilder);
        bufferedReader.close();
    }

    private static int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private static int upperBound(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}

3. 정리

• 이진 검색을 사용하여 target 이상과 이하의 첫 번째 위치를 찾는 lowerBound와 upperBound 메서드를 구현한다.

• 이진 검색을 적용하기 위해 점의 위치를 저장한 배열을 정렬한다.

• 시작점과 끝점을 입력받아 lowerBound와 upperBound 메서드를 사용해 해당 범위의 인덱스를 구한다.

• 끝 인덱스에서 시작 인덱스를 뺀 뒤 1을 더해 선분 안에 포함된 점의 개수를 계산한다.

4. 코드 정리 전

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int[] p = new int[n];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(p);
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int s = Integer.parseInt(stringTokenizer.nextToken());
            int e = Integer.parseInt(stringTokenizer.nextToken());
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (p[mid] < s) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            s = l;
            l = 0;
            r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (p[mid] > e) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            e = r;
            stringBuilder.append(e - s + 1).append("\n");
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

• 이진 탐색 부분을 메서드로 뺐을 때 성능이 더 향상되었다.

• 성능 향상의 원인은 아마 JVM의 최적화, 특히 인라이닝과 조건 분기 단순화에서 비롯된 것으로 보인다.

• 코드가 간결하고 명확해지면 JVM이 이를 더 효과적으로 분석하고 최적화할 수 있어 메서드 분리로 성능이 향상된다.