백준 (BOJ) 20495 수열과 헌팅 java

 

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

20495번: 수열과 헌팅

 

 

일반적인 이분 탐색과 다르게,

 

lower_bound와 upper_bound의 필요성을 잘 이해해야 풀 수 있는 문제.

 

수열의 인덱스가 1부터 시작하므로

 

upper_bound에 1을 빼주는 대신,

 

lower_bound에 1을 더해주는 방식으로 범위 처리를 하면 깔끔하다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] a = new int[N];
        int[] b = new int[N];

        int[] aMinus = new int[N];
        int[] aPlus = new int[N];

        int[] originalMinus = new int[N];
        int[] originalPlus = new int[N];

        StringTokenizer st;
        for(int i=0; i<N; ++i){
            st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
            aMinus[i] = a[i] - b[i];
            aPlus[i] = a[i] + b[i];

            originalMinus[i] = aMinus[i];
            originalPlus[i] = aPlus[i];
        }

        // 1. 정렬하면서 원래 배열을 잃기 때문에 오리지널 배열 하나 더 선언해주어야 한다.
        Arrays.sort(aMinus);
        Arrays.sort(aPlus);

        int l, h, mid;

        StringBuilder sb = new StringBuilder();

        // 범위 탐색
        for(int i=0; i<N; ++i){
            // 이분 탐색 시작 --> ( 탐색 mid 값 = 인덱스 )

            // 범위 '최솟값' 탐색
            l = 0;
            h = N;
            while (l<h){
                mid = (l+h) >> 1;
                if(aPlus[mid] < originalMinus[i]){
                    l = mid + 1;
                }
                else{
                    h = mid;
                }
            }
            sb.append(h+1).append(" ");
            // 1을 더해주는 이유가 있다.
            // 보통 정확한 범위는 l_bound <= x <= u_bound-1이다.
            // upper가 하나 초과한 값이기 때문이다.
            // 하지만 본 문제에서는 수열의 인덱스가 1부터 시작하므로 upper는 놔두고 lower에 1을 더한다.

            // 범위 '최댓값' 탐색
            l = 0;
            h = N;
            while (l < h){
                mid = (l+h) >> 1;
                if(aMinus[mid] <= originalPlus[i]){
                    l = mid + 1;
                }
                else{
                    h = mid;
                }
            }
            sb.append(h).append("\n");
        }

        System.out.print(sb);
    }
}