두 개의 배열
면접 대비시간 제한2초메모리 제한512 MB
A의 각 원소에 대해 B에서 값이 가장 가까운 원소를 찾고(동률이면 더 작은 값) 이 값들의 합을 출력한다.
문제
정수 배열 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 = [16, 8, 12], B = [20, 5, 14, 9]이다.
이때 배열 C는 [14, 9, 14]이므로 정답은 14+9+14 = 37이다.
세 번째 테스트의 경우 C = [2, 2, 3]이며 정답은 7이다.