백준 17124 - 두 개의 배열 (자바 - 이분탐색)

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

17124번: 두 개의 배열

 

문제 요약

정수 배열 A와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다.

A, B 를 이용해서 길이가 n인 새로운 배열 C를 만들어보자.

- C[i] 는 배열 B에 있는 값중 A[i] 에 가장 가까운 값 (절대값 차이가 가장 작은 값) 으로 정의된다.

- 만약 이 조건을 만족하는 값들이 여럿 있는 경우, 그 중 가장 크기가 작은 값으로 정의된다.

 

예를 들어 A = [20, 5, 14, 9] 그리고 B = [16, 8, 12] 라고 해보자.

- C[1] = 16이다. 왜냐하면 B[1] = 16 이 A[1] = 20에 가장 가깝기 때문이다.

- C[2] = 8이다. 왜냐하면 B[2] = 8 이 A[2] = 5에 가장 가깝기 때문이다.

- C[3] = 12이다. 왜냐하면 B[1] = 16와 B[3] = 12 모두 A[3] = 14에 가장 가깝지만, B[3]의 값이 더 작기 때문이다.

- C[4] = 8이다.

이 예제의 경우 C = [16, 8, 12, 8] 로 정의된다.

 

두 배열 A와 B가 주어졌을 때, 새로운 배열 C를 계산하여 배열 C에 포함된 값들의 합을 구하는 프로그램을 작성하시오.

 

* 입력

첫 줄에 테스트 케이스의 수 T (1 <= T <= 10) 가 주어진다.

각 테스트 케이스는 세 줄에 걸쳐서 주어진다.

첫 줄에는 n과 m이 공백으로 구분되어 주어진다. (1 <= n, m <= 10^6) 

두 번째 줄에는 공백으로 구분된 n개의 정수가 주어지며, A[1] 부터 A[n] 을 나타낸다. (각각의 값은 1이상, 10^9 이하이다.)

세 번째 줄에는 공백으로 구분된 m개의 정수가 주어지며, B[1] 부터 B[m] 을 나타낸다. (각각의 값은 1이상, 10^9 이하이다.)

앞서 언급한대로, A와 B는 각각 서로 다른 양의 정수들을 포함한 배열들이다.

 

* 출력

각 테스트 케이스에 대해 배열 C를 구하고, 해당 배열의 모든 원소 합을 한 줄에 출력하시오.

 

* 예시

 

* 해결 과정

입력받은 각 배열의 데이터들을 a, b 배열에 각각 저장하고 b배열만 오름차순 정렬을 수행해준다.

a배열의 경우 입력이 들어온 순서대로 그에 비슷한 숫자를 b배열에서 찾아야 하므로 정렬을 해주어서는 안된다.

이후 a배열을 반복문을 통해 순차탐색 하면서, 각 인덱스에 해당하는 값에 대해 다음과 같이 b배열을 대상으로 이분탐색을 수행해준다.

1. start 는 0, end는 m - 1 값으로 초기화 해준다.

2. start + 1 < end 조건을 만족하는 동안 다음과 같이 반복을 수행해준다.

  - mid 값을 (start + end) / 2 로 초기화 해준다.

  - 만약 현재 a배열에서 탐색중인 값과 b배열에서 mid 인덱스에 해당하는 값이 일치할 경우, c배열에서 현재 탐색중인 인덱스 위치에 그 값을 그대로 저장시켜 주고 이분탐색을 종료시킨다.

  - 만약 현재 a배열에서 탐색중인 값이 b배열에서 mid 인덱스에 해당하는 값 보다 크다면, start 를 mid 값으로 초기화시켜서 mid 값이 더 커지는 방향으로 범위를 줄여준다.

  - 만약 현재 a배열에서 탐색중인 값 보다 b배열에서 mid 인덱스에 해당하는 값이 크다면, end 를 mid 값으로 초기화시켜서 mid 값이 더 작아지는 방향을 범위를 줄여준다.

3. 이분탐색이 끝나고 난 이후, 만약 이분탐색 도중에 a배열에서 탐색중인 값과 b배열에서 mid 인덱스에 해당하는 값이 일치하는 경우를 발견하지 못했다면 다음과 같이 조건에 따라 처리해준다.

  - 만약 현재 a배열에서 탐색중인 값에서 b배열에서 최종적인 start 인덱스에 해당하는 값을 뺀 후, 이를 abs() 메소드를 통해 절댓값으로 변환해준 값 보다, 최종적인 end 인덱스에 해당하는 값을 뺀 후 이를 abs() 메소드를 통해 절댓값으로 변환해준 값이 크거나 같다면, c배열의 현재 탐색중인 위치에 해당하는 인덱스 값에 b배열의 start 인덱스에 해당하는 값을 저장시켜준다.

  - 만약 end 인덱스에 해당하는 값을 뺀 후 abs() 메소드를 통해 절댓값으로 변환해준 값이 더 작다면, c배열의 현재 탐색중인 위치에 해당하는 값에 b배열의 end 인덱스에 해당하는 값을 저장시켜준다.

4. 위의 과정을 통해 c배열이 완성되었다면 최종적으로 배열의 값들을 합산하여 출력해준다.

 

* 코드

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 NumberFormatException, IOException {
        new Main().solution();
    }

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

        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);

            int a[] = new int[n];
            int b[] = new int[m];

            input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                a[j] = Integer.parseInt(input[j]);
            }

            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                b[j] = Integer.parseInt(input[j]);
            }

            Arrays.sort(b);

            int[] c = new int[n];
            for (int j = 0; j < n; j++) {
                int number = a[j];

                boolean check = false;
                int start = 0;
                int end = m - 1;
                while (start + 1 < end) {
                    int mid = (start + end) / 2;

                    if (number == b[mid]) {
                        check = true;
                        c[j] = number;
                        break;
                    } else if (number > b[mid]) {
                        start = mid;
                    } else if (number < b[mid]) {
                        end = mid;
                    }
                }
                if (!check) {
                    if (Math.abs(number - b[start]) == Math.abs(number - b[end])) {
                        c[j] = b[start];
                    } else if (Math.abs(number - b[start]) < Math.abs(number - b[end])) {
                        c[j] = b[start];
                    } else if (Math.abs(number - b[start]) > Math.abs(number - b[end])) {
                        c[j] = b[end];
                    }
                }
            }

            long result = 0;
            for(int j = 0; j < c.length; j++){
                result += c[j];
            }
            bw.write(result + "\n");
        }

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

 

b배열을 오름차순 정렬시킨 후, a배열에서 현재 탐색중인 값과 가장 가까운 값을 b배열에서 특정한 조건에 따라 범위를 절반씩 줄여가며 찾아주었으므로 이분탐색 문제에 해당된다.