[백준] 2470 두 용액 - Java

 

 

 

해당하는 용액을 빠르게 찾아야 한다.

 

먼저 이분 탐색을 활용해 풀어보자.

 

용액의 특성값 합이 0에 가장 가까워야 한다. 용액에 대해 오름차순으로 정렬을 수행한 후, target을 -arr[i]로 설정하고 이분 탐색을 진행하자.

 

1. target이 특성값 배열의 최댓값보다 크면 R + 1을 반환한다.

2. 1의 경우가 아니면 target과 가장 근접한 요소의 인덱스를 반환한다.

 

이진 탐색 코드는 자주 사용되니, 정형화된 스타일을 익혀 두자.

 

 

import java.util.*;
import java.io.*;
 
public class Mabn{	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		int[] arr = new int[N+1];
 
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		for(int i=1; i<N+1; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
 
		Arrays.sort(arr, 1, N+1);
 
		int ans = 2147483647;
		int left_ans = 0;
		int right_ans = 0;
 
		for(int i=1; i<N+1; i++){
			int result_idx = BinarySearch(arr, i+1, N, -1 * arr[i]);
            // 이분탐색 ㄱㄱ 0에 가장 가까워야되니 -1붙인거를 타겟으로 설정.
 
			if(i + 1 <= result_idx - 1 && result_idx - 1 <= N && Math.abs(arr[result_idx - 1] + arr[i]) < ans){
                // 구간 내에 있어야 답 갱신함
				ans = Math.abs(arr[result_idx - 1] + arr[i]);
				left_ans = arr[i];
				right_ans = arr[result_idx - 1];
			}
 
			if(i + 1 <= result_idx && result_idx <= N && Math.abs(arr[result_idx] + arr[i]) < ans){
                // 구간 내에 있어야 답 갱신함 찾지 못한 경우에 대비해 2번 검사한다.
				ans = Math.abs(arr[result_idx] + arr[i]);
				left_ans = arr[i];
				right_ans = arr[result_idx];
			}
 
			
		}
 
 
		System.out.println(left_ans + " " + right_ans);
 
		
 
	}
 
	static int BinarySearch(int[] arr, int L, int R, int target){
			int result = R + 1;
            // 해당하는 경우가 없으면 R+1 리턴.
 
			while(L <= R){
				int mid = (L + R) / 2;
				if(arr[mid] >= target){
					result = mid;
					R = mid - 1;
				}else{
					L = mid + 1;
				}
			}
 
			return result;
	}
}

 

 

 

 

 

이번에는 투 포인터 방법을 활용해서 문제를 풀어보자.

 

 

먼저 용액을 정렬한 후, 특성값이 가장 작은 용액 / 특성값이 가장 큰 용액 이렇게 두 개의 포인터를 설정하자.

 

1. 특성값 최소 + 특성값 최대 < 0

특성값이 최소인 용액은 고려할 필요가 없어진다.

 

2. 특성값 최소 + 특성값 최대 > 0 

특성값이 최대인 용액은 고려할 필요가 없어진다.

 

위 작업을 탐색을 마칠 때 까지 반복한다.

 

 

import java.util.*;
import java.io.*;

public class Main{	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] arr = new int[N+1];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for(int i=1; i<N+1; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, 1, N+1);

		int ans = 2147483647;
		int left_ans = 0;
		int right_ans = 0;

		int L = 1;
		int R = N;

		while(L < R){
			int sum = arr[L] + arr[R];
			if(Math.abs(sum) < ans){
				ans = Math.abs(sum);
				left_ans = arr[L];
				right_ans = arr[R];
			}

			if(sum > 0){
				R--;
			}else{
				L++;
			}

		}

		System.out.println(left_ans + " " + right_ans);

		
		

	}
}