[백준 14921] 용액 합성하기 [Java]

문제

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

---

 

풀이

N개의 수 중 두 수의 합을 0에 최대한 가깝게 만드는 문제다.

우선, A를 오름차순으로 정렬해 문제를 단순화하자.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Init
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // Input
        final int N = Integer.parseInt(br.readLine());
        int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // Solve
        Arrays.sort(A);

정렬된 A에 대해 투포인터 전략으로 두 수의 합이 0에 가까워 지도록 만들어보자.

가장 작은 A[0], 가장 큰 A[N - 1]부터 범위를 좁혀보자.

        int left = 0, right = N - 1;
        int min = Integer.MAX_VALUE, B = 0;
        while (left < right) {
            int sumAB = A[left] + A[right];

두 수의 합 sumAB 의 절댓값이 min 보다 작다면, min을 갱신해주자.

이때, 정답으로 출력해야 하는 수는 절댓값이 아니므로 min이 아닌 B에 기록해주자.

            if (Math.abs(sumAB) < min) {
                min = Math.abs(sumAB);
                B = sumAB;
            }

이제 sumAB에 값에 따라 다음 탐색 범위를 조정해야 한다.

0보다 크다면 right를 감소, 작다면 left를 증가시키면 된다.

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

        // Output
        System.out.print(B);
    }
}

---

소스코드

보기