백준17124-두 개의 배열, java

[백준17124] 두개의 배열 문제 풀이, java

 

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를 구하고 해당 배열의 모든 원소 합을 한 줄에 출력하시오.

풀이

• B배열을 정렬한다
• binarySearch 활용해서 A배열의 값보다 같거나 큰 숫자를 찾는다
• binarySearch  로 찾은 것은 u_index 이며 B[u_index]는 A값보다 크거나 같은 숫자이다
• u_index - 1 를 l_index라고 정의하고 A값과 가까운 값을 찾는다.
• 주의 점은 binarySearch는 배열에 같은 값이 없다면 위치정보를 음수로 반환한다
• 음수로 반환된 값에 +1 후 절대값을 취해주면 index를 찾을 수 있다.
• 시간복잡도는 O(Nlog(M)) 이다
• 다르게 푸는 방법은 A, B배열 둘다 정렬하고 two-pointer로 풀어도 되고 중복 된 값은 메모이제이션해도 된다

package B17124;

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

/**
 * https://www.acmicpc.net/problem/17124
 * title : 두 개의 배열
 * @author tempcru
 * 
 * 두개의 배열이 주어진다
 * 모든 A 배열의 숫자를 새로운 값으로 변경한다
 * 변경기준은 A배열의 숫자와 가장근접한 B배열의 숫자로 변경한다
 * 
 * A배열의 길이가 100만이고 10개TC를 2초안에 통과해야하므로
 * O(NlogM) 혹은 O(N+M) 시간복잡도로 해결한다
 * 
 * B배열을 정렬한후 이분탐색으로 해결하거나
 * A,B배열 정렬한 후 two pointer 개념으로 해결가능할 것 같다.
 */
public class Main {

	// T : [1, 10]
	static int T;
	static long result;
	
	// N, M : [1, 100만]
	static int N, M;
	static int A[];
	static int B[];
	
	
	public static void main(String[] args) throws Exception {

//		System.setIn(new FileInputStream("./src/B17124/sample_data"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		T = Integer.parseInt(br.readLine().trim());
		
		for (int tc = 0; tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			A = new int[N];
			B = new int[M];
			
			// read A
			st = new StringTokenizer(br.readLine().trim());
			for(int i = 0; i < N; i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			// read B
			st = new StringTokenizer(br.readLine().trim());
			for(int i = 0; i < M; i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			//B 정렬
			Arrays.sort(B);
			
			result = 0;
			int l_index = 0;
			int u_index = 0;
			for(int i = 0; i < N; i++) {
				u_index = Arrays.binarySearch(B, A[i]);
				
				if(u_index < 0) {
					u_index = (u_index + 1) * (-1) ;
				}
				
				if(u_index >= M ) {
					u_index--;
				}
				
				if (u_index > 0) {
					l_index = u_index - 1;
				}
				
				result += getMatchedNumber(A[i], l_index, u_index);
				
			}
			
			System.out.println(result);
			
		}
	}


	private static long getMatchedNumber(int target, int l_index, int u_index) {

		int dif_l = Math.abs(target - B[l_index]);
		int dif_u = Math.abs(target - B[u_index]);
		
		if (dif_l > dif_u) {
			return B[u_index];
		} else  {
			return B[l_index];
		}
	}

}