문제 바로가기

나의 풀이

최악의 경우 1,000,000,000이 5000개 들어있는 배열이 input으로 들어올 수 있으므로 이런 큰 수를 다룰때는 처음부터 long type으로 명시해두는 것이 좋다. 다만 인덱스를 담는 변수나 배열은 int 형으로 선언하였다.

이 문제를 브루트포스로 풀려면 O(n3) 의 시간 복잡도를 가지므로 안된다.

또한, start와 mid 값은 이중 for문으로 돌리고 그 합에 (-)를 씌운 값을 이분탐색으로 찾는 방식도 생각해봤다. O(n2logn) 의 시간 복잡도를 가지므로 이것 또한 불가능하다.

보통 코딩테스트에서는 1억번의 연산에 1초가 걸리므로 n = 1000인 경우 O(n2logn) 은 3초정도가 걸릴 것이다.

따라서 이 문제는 투포인터를 응용해서 풀어야 시간초과가 나지 않는다.

투포인터는 이중 for문의 시간 복잡도 O(n2)을 선형 시간 O(n)으로 해결해준다.

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

class Main {

    // input 값이 들어오는 배열 선언
    static long[] arr;
    // 선택하는 3개의 인덱스 값을 넣을 배열 선언
    static int best[] = new int[3];
    // 세 포인터
    static int start, mid, end;
    static long min = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        arr = new long[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        // 투포인터 문제에서는 정렬이 필수적이다
        Arrays.sort(arr);

        // 투포인터의 응용으로 start는 for 문으로 하나씩 늘려가고, mid와 end를 각각 투포인터로 해결
        for (int i = 0; i < n - 2; i++) {
            start = i;
            mid = i + 1;
            end = n - 1;
            while (mid < end) {
                long sum = arr[start] + arr[mid] + arr[end];
                if (min > Math.abs(sum)) {
                    min = Math.abs(sum);
                    best[0] = start;
                    best[1] = mid;
                    best[2] = end;
                }
                if (sum == 0) {
                    break;
                } else if (sum > 0) {
                    end--;
                } else {
                    mid++;
                }
            }
        }
        System.out.println(arr[best[0]] + " " + arr[best[1]] + " " + arr[best[2]]);
    }
}