1 분 소요

문제

문제 바로가기

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력한다. 출력해야하는 세 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

접근방법

문제는 매우 간단하다. 먼저 배열을 정렬한 후에 작은 값부터 하나를 선택하고 나머지 두 수를 이분 탐색을 통해 찾는다. 세 수의 합이 0보다 작으면 두 번째 수를 증가시키고, 0보다 크면 세 번째 수를 감소시킨다. 합이 0이 되면 바로 세 수를 출력한다.

풀이

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

public class Main {
    static long min = Long.MAX_VALUE;
    static int N;
    static boolean check;
    static long[] arr;
    static long res1, res2, res3;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        for(int i = 0; i < N-2; i++) {
            binarySearch(i+1, N-1, arr[i]);
            if(check)
                break;
        }

        bw.write(res1 + " " + res2 + " " + res3 + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void binarySearch(int left, int right, long num) {
        while(left < right) {
            long sum = num + arr[left] + arr[right];
            long tmp = Math.abs(sum);

            if(min > tmp) {
                min = tmp;
                res1 = num;
                res2 = arr[left];
                res3 = arr[right];
            }

            if(sum < 0) left++;
            else if(sum > 0) right--;
            else {
                check = true;
                break;
            }
        }
    }
}

댓글남기기

참고