BOJ (Java) 2473번: 세 용액

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

 

---

풀이

합이 최소가 되는 두 수를 고르는 것과 원리는 동일하다.

세 개의 수를 골라야 하므로 하나의 수를 기준으로 세워두고 투 포인터로 탐색, 합이 최소가 되는 세 개의 수를 찾는다.

---

Java 코드

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

public class Main {

    private static int N;
    private static long[] values;

    private static long[] minValues = new long[3];
    private static long answer = 4_000_000_000L;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        values = new long[N];
        String[] inputs = bf.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            values[i] = Integer.parseInt(inputs[i]);
        }

        // 오름차순으로 정렬 후 하나의 숫자를 기준으로 삼아 투 포인터 실행
        Arrays.sort(values);
        for (int i = 0; i < N; i++) {
            getZero(i);
        }

        // 오름차순으로 정렬 후 출력
        Arrays.sort(minValues);
        System.out.printf("%d %d %d\n", minValues[0], minValues[1], minValues[2]);
    }

    private static void getZero(int idx) {
        // 인덱스 안 겹치게 초기화
        int start = idx == 0 ? 1 : 0;
        int end = idx == N - 1 ? N - 2 : N - 1;

        while (start < end) {
            long nowSum = values[idx] + values[start] + values[end];

            // 최솟값 갱신
            if (Math.abs(nowSum) < answer) {
                answer = Math.abs(nowSum);
                minValues[0] = values[idx];
                minValues[1] = values[start];
                minValues[2] = values[end];
            }
            
            // 인덱스를 옮겼을 때 값이 더 작아지는 방향으로 이동
            if (start < N && Math.abs(values[idx] + values[start + 1] + values[end])
                    < Math.abs(values[idx] + values[start] + values[end - 1])) {
                start++;
            } else {
                end--;
            }

            // 기준이 되는 인덱스와 안 겹치게 인덱스 조정
            if (start < N && start == idx) {
                start++;
            }
            if (0 < end && end == idx) {
                end--;
            }
        }
    }
}