백준 26168 - 배열 전체 탐색하기 (자바 - 이분탐색)

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

26168번: 배열 전체 탐색하기

 

* 문제 요약

크기 n인 정수형 배열 A가 주어진다. 배열 A의 원소는 A[0], A[1], ... A[n-1] 이다. 배열 A에는 같은 값을 갖는 원소가 여러개 존재할 수 있다. 

배열 A에 대한 m개의 질의가 저장된 배열 B가 주어진다. 배열 B에 저장된 m개의 질의는 아래 세 가지 유형으로 구분된다.

첫 번째가 유형1, 두 번째가 유형2, 세 번째가 유형3 이다.

- 1 k : 배열 A의 원소 중 k 보다 크거나 같은 원소의 갯수를 출력한다.

- 2 k : 배열 A의 원소 중 k 보다 큰 원소의 갯수를 출력한다.

- 3 i j : 배열 A의 원소 중 i보다 크거나 같고 , j보다 작거나 같은 원소의 갯수를 출력한다.

배열 B에 저장된 첫 번째 질의부터 m번째 질의까지 순서대로 처리하면서 질의 결과를 출력하자.

 

* 입력

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 배열 A의 원소 A[0], A[1], ...  A[n-1] 이 공백을 사이에 두고 순서대로 주어진다.

세 번째 줄부터 m개의 줄에 걸쳐 배열 B에 저장된 m개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 정수가 공백을 사이에 두고 순서대로 주어진다.

 

* 출력

첫 번째 줄부터 질의 결과를 순서대로 한 줄씩 출력한다.

 

* 제한

- 1 <= n, m <= 100,000

- 1 <= A[i] <= 10^18 (0 <= i <= n-1)

- 1 <= i <= j <= 10^18

- 1 <= k <= 10^18

 

* 예시

 

* 해결 과정

이 문제를 해결하기 위해서는 다음과 같은 두 가지 경우에 조건에 맞는 값을 구할 수 있어야 한다.(lowerBound, upperBound)

1. 오름차순으로 정렬된 int 형 배열에서 중복되는 값이 존재하는 경우 특정값이 나오는 첫 번째 인덱스를 구하기.

- 조건 1과 3에서 특정값 보다 크거나 같은 숫자의 갯수를 구할 때 활용될 수 있다.

- 특정값이 나오는 첫 번째 인덱스를 발견하면 현재 배열이 오름차순으로 정렬되어 있으므로 그 뒤에 있는 숫자들은 모두 특정값보다 크거나 같은 숫자들이기 때문이다.

2. 오름차순으로 정렬된 int 형 배열에서 중복되는 값이 존재하는 경우 특정값이 아닌 원소가 나오는 첫번째 인덱스를 구하기

- 조건 2와 3에서 특정값 보다 큰 값, 특정값 보다 작거나 같은 값을 구할 때 활용될 수 있다.

- 특정값이 아닌 원소가 나오는 첫 번째 인덱스가 발견될 경우 현재 배열이 오름차순으로 정렬되어 있으므로 해당 인덱스부터 배열의 마지막 원소까지는 모두 특정값 보다 큰 숫자들이라는 뜻이다.

- 여기서 특정값이 아닌 원소가 나오는 첫 번째 인덱스에 -1을 하면 바로 왼쪽에 있는 인덱스로 이동하게 되는데, 이 인덱스 값 부터 배열의 가장 앞에있는 원소까지는 모두 특정값 보다 작거나 같은 숫자들에 해당된다.

 

위의 두 가지 경우에 조건에 맞는 값을 구하는 방법을 이용하여 다음과 같이 로직을 작성할 수 있다.

1. 처음 입력받는 데이터들을 배열에 저장해준 뒤 오름차순으로 정렬해준다.

2. 조건 1이 입력으로 들어온 경우 입력으로 들어온 배열에서 (중복이 존재함) 그 뒤에 따라온 숫자가 첫 번째로 등장하는 인덱스를 찾아서 반환해준 다음, 해당 값을 배열 길이 n에서 빼준값을 출력해준다.

- n에서 특정값이 처음으로 나오는 인덱스를 빼주면, 그 결과값은 자연스럽게 특정값 보다 크거나 같은 값들의 갯수가 된다.

3. 조건 2가 입력으로 들어온 경우 입력으로 들어온 배열에서 (중복이 존재함) 그 뒤에 따라온 숫자가 아닌 원소가 나오는 첫 번째 인덱스를 찾아서 반환해준 다음, 해당 값을 배열 길이 n에서 빼준 값을 출력해준다.

- n에서 특정값이 아닌 원소가 나오는 첫 번째 값의 인덱스를 빼주면, 그 결과값은 자연스럽게 특정값 보다 큰 숫자들의 갯수가 된다.

4. 조건 3이 입력으로 들어온 경우 두 가지 탐색을 동시에 수행해준다.

- 이후에 따라온 숫자 i, j 에 대해 배열에서 i 가 최초로 등장하는 인덱스와 j 가 아닌 원소가 최초로 등장하는 인덱스를 반환해준다.

- i <= j 가 기본 조건인데 배열은 오름차순으로 정렬되어 있으므로 통상 j 가 아닌 원소가 최초로 등장하는 인덱스가 i가 최초로 등장하는 인덱스보다 크거나 같게 된다. 그러므로 j 가 아닌 원소가 최초로 등장한 인덱스에서 i 가 최초로 등장한 인덱스 값을 빼준 다음, 그 값에 +1을 해준다. 

(배열 인덱스가 0 부터 시작하는 특징이 있기 때문에 정확한 갯수를 구하려면 +1 을 해주어야 한다.)

- 해당 값의 결과는 i 보다 크거나 같고, j 보다 작거나 같은 값들의 갯수가 된다. (두 숫자 i 와 j 를 포함한 인덱스간의 격차가 곧 조건3을 만족하는 숫자들의 범위가 된다.)

 

* 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static long[] arrayA = null;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        arrayA = new long[n];

        input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arrayA[i] = Long.parseLong(input[i]);
        }

        Arrays.sort(arrayA);
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int category = Integer.parseInt(input[0]);
            long number = Long.parseLong(input[1]);

            int numberCount = 0;
            if (category == 1) {
                // 크거나 같은 값 갯수
                numberCount = n - lowerBound(number);
                bw.write(numberCount + "\n");

            } else if (category == 2) {
                // 큰 값 구하기
                numberCount = n - upperBound(category, number);
                bw.write(numberCount + "\n");
            } else if (category == 3) {
                // i보다 크거나 같고, j 보다 작거나 같은 값
                long number2 = Long.parseLong(input[2]); // j

                numberCount = lowerBound(number);
                long jCount = upperBound(category, number2);
                bw.write((jCount - numberCount + 1) + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 중복이 존재하는 배열에서 특정값이 나오는 첫번째 인덱스를 구함(크거나 같은 숫자 갯수 구하기)
    private int lowerBound(long number2) {
        int start = 0;
        int end = arrayA.length;

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

            if (number2 <= arrayA[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // 중복이 존재하는 배열에서 특정값이 아닌 원소가 나오는 첫번째 인덱스(특정값보다 큰 값 구하기, 작거나 같은 값 구하기)
    private int upperBound(int category, long number) {
        int start = 0;
        int end = arrayA.length;

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

            if (arrayA[mid] <= number) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (category == 2) {
            // 큰 값
            return start;
        } else {
            // 작거나 같은 값
            return start - 1;
        }
    }
}

 

중복이 존재하는 배열에 대해 특정값이 최초로 나오는 경우의 인덱스(lowerBound), 특정값이 아닌 원소가 최초로 나오는 경우의 인덱스 (upperBound) 를 이분탐색의 방식으로 구해준 다음, 문제에서 요구하는 각 조건에 맞는 숫자들의 갯수를 구해주었으므로 이분탐색 문제에 해당된다.