[JAVA]BOJ 2470, 두 용액

두 포인터를 사용하는 문제이다. 

 

1. 입력을 받고 오름차순으로 정렬한다.

2. [0]과 [N-1]자리에 각각 포인터를 두고 0에 가까워지도록 만든다.

3. 0에 가장 가까울때의 값을 출력한다.

 

1. 입력받고 오름차순 정렬

쉬우니까 생략

 

2. [0]과 [N-1]자리에 각각 포인터를 두고 0에 가까워지도록 만든다.

예시를 먼저 들면.. 배열이 아래와 같을때 첫번째 계산을 한다. N = 5, *과 **은 포인터이다.

 

-13 -10 -8 11 12 

 [0] [1] [2] [3] [4]

 *                   **

두 용액을 합한다. [0]-13 + [4]12 = -1 가 될것이다. '[0]-13 + [4]12 = -1' 가 0에 근접하려면 어떤 계산을 해야할까?

[0]-13에는 [4]12 보다 더 큰 수(예를들면 13같은)를, [4]12에는 [0]-13 보다 더 큰 수(예를들면 -12같은)를 더하면 된다. 그리고 후자와 같은 방식으로 계산을 할것이다. 

 

설명하기는 좀 어려운데.. 배열에서 [4]12 보다 큰 수는 없고, 설령 있다고 해도 이미 이전에 계산을 하고 [4]12 으로 넘어온 것이라 다시 증가시키지 않는다. 두 포인터가 각각 안쪽으로 움직여야 모든 경우를 다 파악할 수 있다. (--><-- 이런식으로 움직임...)

 

다음으로 용액을 합한다. [1]-10 + [4]12 = 2 가 될 것이다. 아직 0이 아니다. [1]-10에 더 작은 수([3]11)를 합한다.

 

다음 용액을 합한다. [1]-10 + [3]11 = 1 이 된다. 아직 0이 아니다. [3]11 에 더 큰 수([2]-8)를 합한다.

 

다음 용액을 합한다. [2]-8 + [3]11 = 2 이 된다. 아직 0이 아니다. [3]11 에 더 큰 수를 합하..려고하는데 [3]은 자기자신과 같으므로 더 더하지 못한다. 

 

용액을 합하는 각각 계산마다 0에 가까운 합을 저장한다. 그리고 0에 가까운지 비교를 한다. 음수와 비교해야 하므로 절대값으로 비교한다. (-3과 1을 그냥 대소비교하면 -3이 작지만, 절대값인 |3|과 |1|을 비교하면 1이 더 작다.)

비교하고 더 작은경우에 용액 2개를 저장하고 3.출력한다.

// 두 포인터 사용
while (left < right) {
    int sum = arr[left] + arr[right];

    // 현재 합이 0에 더 가까운지 확인 -> 음수 비교를 위해 절댓값 사용
    if (Math.abs(sum) < Math.abs(closestSum)) {
        closestSum = sum;
        sol1 = arr[left];
        sol2 = arr[right];
    }

    // 두 용액의 합이 0과 가까워지도록 포인터 이동 -> 제일 큰 양수, 제일 작은 음수로 계산하기 때문에 아래와 같은 조건을 사용할 수 있음
    if (sum < 0) { // 음수인 경우 0을 만들기 위해 왼쪽에서 더 큰 수 선택
        left++;
    } else { // 양수인 경우 0을 만들기 위해 오른쪽에서 더 작은 수 선택
        right--;
    }
}

---

아래는 전체 코드이다.

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

public class BOJ2470 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i, left = 0, right, closestSum = 1999999999, sol1 = 0, sol2 = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        right = N - 1;

        // 입력
        for (i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 정렬
        Arrays.sort(arr);

        // 두 포인터 사용
        while (left < right) {
            int sum = arr[left] + arr[right];

            // 현재 합이 0에 더 가까운지 확인 -> 음수 비교를 위해 절댓값 사용
            if (Math.abs(sum) < Math.abs(closestSum)) {
                closestSum = sum;
                sol1 = arr[left];
                sol2 = arr[right];
            }

            // 두 용액의 합이 0과 가까워지도록 포인터 이동 -> 제일 큰 양수, 제일 작은 음수로 계산하기 때문에 아래와 같은 조건을 사용할 수 있음
            if (sum < 0) { // 음수인 경우 0을 만들기 위해 왼쪽에서 더 큰 수 선택
                left++;
            } else { // 양수인 경우 0을 만들기 위해 오른쪽에서 더 작은 수 선택
                right--;
            }
        }

        // 정답 출력
        System.out.println(sol1 + " " + sol2);
    }
}

처음에 이진탐색으로 풀었다가 시간초과가 났다. 심지어 예외처리도 엄청 많이했고... 음수에 양수만 더하는 방식으로 해서 괜찮을 줄 알았는데.. O(n^2)이라 넘은 것 같다. 만약 양수 음수 반반 찬 배열이라면 1/2N^2이라 혹시몰라서 해봣는데 이것도 O(n^2)긴하니까.. 내 코드가 틀려서 아쉽지만 그래도 공부가 되었다.

아쉬우니까 시간초과 코드도 올려야지ㅎ

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, i, j, sol1 = 0, sol2 = 0 , searchResult, min = 999999999, calcResult;
        String str;
        StringTokenizer st;

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

        int[] arr = new int[N];

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

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

        // 정렬
        Arrays.sort(arr);

        // 전부 음수&양수 인 경우
        if(arr[0] >= 0){ // 전부 양수
            sol1 = arr[0];
            sol2 = arr[1];
        }
        else if(arr[N - 1] <= 0){ // 전부 음수
            sol1 = arr[N - 2];
            sol2 = arr[N - 1];
        }
        else{ // 음수&양수 섞인 경우
            // 1. 정확히 일치하는 양수가 있는 경우 == 두 용액의 합이 0인 경우
            for(i=0;arr[i]<0;i++){
                searchResult = Arrays.binarySearch(arr, -arr[i]);
                if(searchResult > 0){
                    sol1 = arr[i];
                    sol2 = arr[searchResult];
                    break;
                }
            }

            // 2. 없는 경우 -> binarySearch 반환값이 -insertoinPoint -1 인 것을 이용(해당 값이 없을때)
            if(sol1 == sol2){ // 1.에서 정답을 찾지 못한 경우에 2. 실행
                searchResult = Arrays.binarySearch(arr, 0);
                for(i=0;arr[i]<0;i++){
                    for(j=N-1;j>= -(searchResult + 1);j--){
                        calcResult = arr[i] + arr[j];
                        calcResult = (calcResult < 0) ? -calcResult : calcResult; // 계산 결과 음수인 경우 양수로 바꾸기
//                        System.out.println(arr[i] +" "+ arr[j] +" "+calcResult);

                        if(calcResult < min){ // 0에 근접한지 비교
                            min =  calcResult;
                            sol1 = arr[i];
                            sol2 = arr[j];
                        }
                    }
                }
                //제일 작은 양수끼리의 합이랑 제일 큰 음수끼리의 합 비교
                if(arr[-(searchResult + 1)] + arr[-(searchResult)] < min){
                    sol1 = arr[-(searchResult + 1)];
                    sol2 = arr[-(searchResult)];
                }
                else if(-(arr[-(searchResult + 3)] + arr[-(searchResult + 2)]) < min){
                    sol1 = arr[-(searchResult + 3)];
                    sol2 = arr[-(searchResult + 2)];
                }
            }
        }

        // 정답 출력
        System.out.println(sol1 + " " + sol2);