[자바] 백준 2470 - 두 용액 (boj java)

문제 : boj2470

 

  예시 입력 1을 봐보자.

5
-2 4 -99 -1 98

위 상태로만 보자면, 결국 O(N^2)으로 모든 쌍을 확인하는 것 외에 별다른 방법이 떠오르지 않을 것이다.

 

정렬을 하면 어떨까?

-99

-2

-1

4

98

이 경우 가장 좌측에서 시작하는 포인터를 s, 가장 우측을 e라고 해보자.

's의 값 + e의 값'을 기준으로 포인터를 중앙으로 점차 가져와보자.

- 두 포인터가 가르키는 값의 합이 0 초과이라면 -> 더 작은 값을 확인해야하니 e를 좌측으로 이동한다.

- 두 포인터가 가르키는 값의 합이 0 미만이라면 -> 더 큰 값을 확인해야하니 s를 우측으로 이동한다.

 

위 두가지 경우에 따라 s와 e를 중앙으로 이동시키면서 0과 가장 가까운 값을 찾으면 된다!

위의 경우

1. s=-99, e=98 이므로 s+e는 -1

2. 음수이므로 s를 우측으로 전진해서 s=-2, e=98 이므로 s+e는 96

3. 양수이므로 e를 좌측으로 -> s=-2, e=4, s+e=2

4. 양수이므로 e를 좌측으로 -> s=-2, e=-1, s+e=-3

5. 음수이므로 s를 우측으로 가려는데 s==e가 됬으므로 종료.

 

위 경우에서 가장 0과 가까운 합은 -1 이므로 -1이 답.

 

 

코드 : github

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

public class Main {
    private static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);

        int s = 0, e = n-1;
        int min = Integer.MAX_VALUE;
        int ansS = 0, ansE = 0;
        while (s < e) {
            int sum = Math.abs(arr[e]+arr[s]);
            if (sum < min) {
                min = sum;
                ansS = s;
                ansE = e;
            }
            if (sum == 0)
                break;

            if (arr[e]+arr[s] > 0) e--;
            else s++;
        }

        System.out.println(arr[ansS] + " " + arr[ansE]);
    }

    public static void main(String[] args) throws Exception {
        solution();
    }
}