[Baekjoon] 2467번: 용액

https://www.acmicpc.net/problem/2467

2467번: 용액

문제 설명

사이트 설명은 길지만 핵심은 오름차순으로 입력되는 수 중 두 수의 합의 절댓값이 0과 가장 가까운 두 수를 찾는 것이다.  

풀이 방법 - 투 포인터

어떻게 보면 완전탐색이지만 투 포인터를 활용하면 더 효율적으로 해결할 수 있다. 예제 입력 1로 시나리오를 생각해보자.

먼저 입력 자체가 오름차순이기 때문에 맨 왼쪽은 가장 작은 수이고 맨 오른쪽은 가장 큰 수이다. 따라서 맨 왼쪽이 양수라면 맨 앞 두 수를 출력하면 되고, 맨 오른쪽이 음수라면 맨 오른쪽에서 두 수를 출력하면 된다. 그 상황을 제외하면 음수와 양수가 순서대로 들어있다.

먼저 맨 왼쪽과 맨 오른쪽 수를 더해본다. 만약 합이 양수라면 양수가 음수보다 더 크다는 뜻이다. 따라서 음수와 양수의 차이를 줄이기 위해서는 양수의 값을 줄여야 한다.

만약 합이 음수라면 음수가 양수보다 더 크다는 뜻이므로 음수의 값을 줄여야 한다. 이제 어느 정도 알고리즘이 떠오를 것이다. 과정을 살펴보자.

준비

• left : 왼쪽부터 나아갈 포인터 변수이다.
• right: 오른쪽부터 뒤로 갈 포인터 변수이다.
• MIN: 최솟값을 저장해두기 위한 변수이다.
• minL: 최솟값이 갱신되었을 때의 left 인덱스를 저장하기 위한 변수이다.
• minR: 최솟값이 갱신되었을 때의 right 인덱스를 저장하기 위한 변수이다.

 

1. nums[L] + nums[R]을 더한 값은 -1이다. 절댓값 1이 현재 최솟값보다 작으므로 MIN과 minL, minR을 갱신한다. 그리고 두 합이 음수이기 때문에 음수를 줄이기 위해 L을 한 칸 앞으로 옮긴다.

1회전

2. 다시 nums[L]과 nums[R]을 더한다. 이젠 96이 된다. 절댓값 96이 현재 최솟값보다 크므로 갱신하지 않는다. 또한 두 합이 양수이므로 양수를 줄이기 위해 R을 한 칸 뒤로 옮긴다.

2회전

3. nums[L] + nums[R] = 2이다. 절댓값 2가 최솟값보다 크므로 갱신하지 않는다. 또한 두 합이 양수이므로 양수를 줄이기 위해 R을 한 칸 뒤로 옮긴다.

3회전

4. nums[L] + nums[R] = -3이다. 절댓값 3이 최솟값보다 크므로 갱신하지 않는다. 또한 두 합이 음수이므로 음수를 줄이기 위해 L을 한 칸 앞으로 옮긴다.

4회전

이렇게 L과 R이 같은 위치에 놓이거나 엇갈리게 되면 모든 수를 탐색한 것이므로 반복을 종료하고 nums[minL]과 nums[minR]을 출력하면 된다.

 

코드는 다음과 같다.

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

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[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        if (nums[0] >= 1) {
            System.out.print(nums[0] + " " + nums[1]);
            return;
        }
        if (nums[N - 1] <= -1) {
            System.out.print(nums[N - 2] + " " + nums[N - 1]);
            return;
        }

        int left = 0, right = N - 1;
        int minL, minR, MIN;
        minL = minR = MIN = Integer.MAX_VALUE;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == 0) {
                System.out.print(nums[left] + " " + nums[right]);
                return;
            }

            int sumAbs = Math.abs(sum);

            if (MIN >= sumAbs) {
                MIN = sumAbs;
                minL = left;
                minR = right;
            }

            if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }

        System.out.print(nums[minL] + " " + nums[minR]);
    }
}