[알고리즘 / 백준] 2470 - 두 용액

www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제는 위와 같으며, 정렬과 투 포인트를 사용하여 문제를 해결하였습니다.

 

먼저 주어진 용액들을 순서대로 정렬하였습니다. 그러고 난 뒤, low와 high 두 포인트를 생성하고 각각 주어진 용액 배열의 가장 앞과 뒤를 가리키도록 하였습니다. 그리고 이때 두 수의 합의 절댓값을 sum 변수에 저장하고 계산에 사용된 두 값을 result 배열에 저장하였습니다. 최종적으로 출력할 때 오름차순으로 출력되기 때문에 low가 가리키는 값을 result[0]에 high가 가리키는 값을 result[1]에 추가하였습니다.

 

그런 다음, low가 high보다 작은 경우를 반복하면서 low가 가리키는 값과 high가 가리키는 값의 합을 구해 그 절댓값이 기존에 구한 sum 보다 더 작은 경우에는 0에 더 가까운 합이기 때문에 sum과 result를 변경해줍니다.

 

그리고 나서 low 또는 high 값을 이동시키는데, 만약 위에서 구한 low가 가리키는 값과 high가 가리키는 값의 합이 양수 또는 0이라고 한다면, high 값을 더 작은 값으로 이동시켜야 low와 더했을 때 조금이라도 0에 가까워질 가능성이 있기 때문에 high 값을 하나 감소시킵니다.

 

만약, low가 가리키는 값과 high가 가리키는 값의 합이 음수인 경우에는, high가 가리키는 값을 줄인다고 해도 결국 더 작은 음수가 나오기 때문에 low를 하나 증가시킵니다.

 

-99 + 98 = -1 이므로, 기존 sum보다 절댓값이 작지 않으므로 변경없이 low가 가리키는 값을 하나 증가시킵니다.

-2 + 98 = 96이므로, 기존 sum보다 절댓값이 작지 않으므로 변경없이 high가 가리키는 값을 하나 감소시킵니다.

-2 + 4 = 2이므로, 기존 sum보다 절댓값이 작지 않으므로 변경없이 high가 가리키는 값을 하나 감소시킵니다.

-2 + (-1) = -3이므로, 기존 sum보다 절댓값이 작지 않으므로 변경없이 low가 가리키는 값을 하나 증가시킵니다.

이 과정을 low와 high가 같아질 때까지 반복하고 나면, 0에 가장 가까운 용액을 만드는 두 용액이 result에 저장되게 되고 이 값들을 차례로 출력하면 됩니다.

 

---

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        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();
        Arrays.sort(nums);  // 오름차순 정렬

        // 초기 low, high 포인트 지정 및 초기 결과, 용액 합의 절댓값 지정
        int low = 0, high = nums.length - 1;
        int[] result = new int[2];
        result[0] = nums[0];
        result[1] = nums[nums.length - 1];
        int sum = Math.abs(result[0] + result[1]);
        
        // low가 high 보다 작을 동안
        while (low < high) {
            int tmp = nums[low] + nums[high];  // low가 가리키는 값과 high가 가리키는 값의 합을 구해서
            // 그 값의 절댓값이 기존에 구한 sum보다 작은 경우 (더 0에 가까운 용액인 경우)
            if (sum > Math.abs(tmp)) {
                sum = Math.abs(tmp);  // 합의 절댓값을 sum에 저장하고
                // 합을 구할 때 사용된 두 수를 저장
                result[0] = nums[low];
                result[1] = nums[high];
            }

            // low가 가리키는 값과 high가 가리키는 값의 합이 0이상인 경우 high 위치 이동
            if (tmp >= 0) {
                high -= 1;
            } else {  // 0이하인 경우 low 위치 이동
                low += 1;
            }
        }

        System.out.println(result[0] + " " + result[1]);
    }
}

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))
nums.sort()

low = 0
high = len(nums) - 1

result = [nums[0], nums[-1]]
s = abs(nums[0] + nums[-1])
while low < high:
    tmp = nums[low] + nums[high]
    if s > abs(tmp):
        s = abs(tmp)
        result[0] = nums[low]
        result[1] = nums[high]

    if tmp >= 0:
        high -= 1
    else:
        low += 1

print(result[0], result[-1])