두 개의 배열

문제

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는 각각 서로 다른 양의 정수들을 포함한 배열들이다.

입출력 예

입력	출력
3
4 3
20 5 14 9
16 8 12
3 4
16 8 12
20 5 14 9
3 3	44
1 2 3	37
2 3 4	7

입출력 예 설명

첫 테스트 케이스는 문제에서 언급되었다.

두 번째 테스트 케이스의 경우 A = [16, 8, 12] 이고 B = [20, 5, 14, 9] 이다.

이 경우 배열 C는 [14, 9, 14] 이며 따라서 정답은 14+9+14 = 37이다.

세 번째 테스트의 경우 C = [2 2 3] 이며 정답은 7이다.

아이디어

b배열을 먼저 정렬한 뒤에 이진탐색을 활용한 문제이다

Arrays에 있는 BinarySearch를 활용하여 반환되는 index를 통해 값을 찾을 수 있다

제출 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class three17124 {
    private long result;
    private int[] a;
    private int[] b;

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();

        for (int test = 0; test < testCase; test++) {
            result = 0;
            int n = sc.nextInt();
            int m = sc.nextInt();
            a = new int[n];
            b = new int[m];

            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            for (int i = 0; i < m; i++) {
                b[i] = sc.nextInt();
            }
            Arrays.sort(b);

            int lIndex = 0;
            int uIndex = 0;
            for (int i = 0; i < n; i++) {
                uIndex = Arrays.binarySearch(b, a[i]);

                // binarySearch는 배열에 같은 값이 없다면 위치 정보를 음수로 반환
                // 음수로 반환된 값에 +1 후 절대값을 취해주면 index를 찾을 수 있음
                if (uIndex < 0) {
                    uIndex = (uIndex + 1) * (-1);
                }
                if (uIndex >= m) {
                    uIndex--;
                }
                if (uIndex > 0) {
                    lIndex = uIndex - 1;
                }
                result += getMatchedNumber(a[i], lIndex, uIndex);
            }
            System.out.println(result);
        }
    }

    private int getMatchedNumber(int target, int lIndex, int uIndex) {
        int diffL = Math.abs(target - b[lIndex]);
        int diffU = Math.abs(target - b[uIndex]);

        if (diffL > diffU) {
            return b[uIndex];
        } else {
            return b[lIndex];
        }
    }

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