백준 2470 - 두 용액 (JAVA 자바 풀이)

백준 2470 - 두 용액 (JAVA 자바 풀이)

 

 

 

투포인터 알고리즘으로 풀었습니다. 

자세한 풀이방법은 아래와 같습니다. 

 

1. 먼저 arr 배열에 주어진 숫자들을 long으로 받아준다.

2. Arrays.sort를 활용해서 정렬해준다. 

3. 투포인터 알고리즘을 활용해서 각각 왼쪽 / 오른쪽에서 포인터 시작점을 잡아주고, 왼쪽포인터는 한칸씩 올려주고 오른쪽포인터는 한칸씩 내려주면서 비교해준다. 

4. 0과 가장 가까운 숫자의 조합을 알아내야 하므로, sum 변수에 두 숫자를 합한 값을 넣어주고 0에서 sum을 뺀값에 절대값을 씌워서 가지고 있는다. 

5. min 변수는 0에서 가장 가까운 숫자를 찾아내기 위한 변수

6. sum값을 도출한 뒤 왼쪽포인터를 우측으로 한칸 옮길지, 아니면 오른쪽포인터를 좌측으로 한칸 옮길지에 대한 판단은 if문을 활용해서 결정해주었다.

 

반례는 아래 반례를 참고해서 풀면 됩니다. 

 

<반례>

입력

4
-3 1 2 10

 

출력

-3 2

 

 

 

 

import java.io.*;
import java.util.*;
 
public class test {
 
    static int N;
    static long arr [];
    static long ans1, ans2;
 
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine()); // 9
        arr = new long [N];
        st = new StringTokenizer(br.readLine());
 
        for (int i=0; i<N; i++){
            arr[i] = Long.parseLong(st.nextToken());
        }
 
        Arrays.sort(arr);
 
 
        // 투 포인터 알고리즘
        int left = 0;
        int right = N-1;
        long sum = 0;
        ans1 = 0;
        ans2 = 0;
        long min = Long.MAX_VALUE;
 
        while(left != right) {
            sum = Math.abs(arr[left] + arr[right]);
            if (sum <= min) {
                ans1 = arr[left];
                ans2 = arr[right];
                min = sum;
            }
            if (Math.abs(arr[left+1] + arr[right]) < Math.abs(arr[left] + arr[right-1])){
                left++;
            }
            else right--;
        }
        // 구현 완료
 
        System.out.println(ans1 + " " + ans2);
 
    }
}