b.2473 세용액

 

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

 

 

 

이 문제는 주어진 농도들 속에서 합이 가장 0에 가까운 3가지 용액조합을

오름차순으로 출력하는 문제이다.

 

용액의 가짓수가 최대 5000에 달하고

농도의 범위가 최대 10억에 해당되어 끝 범위를 잘 체크하여 검사해야한다.

투 포인터를 활용하여 효율적으로 세 수를 탐색하며,
정렬과 반복문을 통해 각 경우를 계산했다.

먼저 입력받은 배열 arr을 정렬하여 오름차순으로 정렬 후
투 포인터 접근법을 사용하여
각 숫자를 고정점(t)으로 선택하고,
나머지 두 숫자는 투 포인터로 탐색한다.

투 포인터는 고정점을 제외한 배열의 양 끝에서 시작하며, 현재 선택된 세 숫자의 합을 계산해 절대값 기준으로 0에 가장 가까운 값을 갱신한다.
twoPointer 메서드는 고정점 t를 제외한 구간에서 두 포인터를 이동하며 합을 계산하는 방식으로

코드를 작성했다..

만약 세 숫자의 합이 0에 가까워지면 이를 갱신하고,
합이 0보다 크면 끝 포인터를 줄이고,
0보다 작으면 시작 포인터를 늘려 다음 탐색을 진행한다.
고정점과 두 포인터를 통해 모든 가능한 세 숫자의 조합을 탐색하며,
가장 최적의 값을 저장한다.

탐색이 끝나면 세 숫자를 오름차순으로 정렬한 뒤 결과를 출력한다. 이 코드는 투 포인터를 사용해 O^2 의 시간 복잡도로 동작한다.

 

 

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

public class Main {

    static int N;
    static long minimum = Long.MAX_VALUE;
    static long[] arr, ans;
    static void twoPointer(int t){
        int start = 0, end = N-1;

        while(start != end-1){
            if(start == t){
                start++;
                continue;
            }else if (end == t){
                end--;
                continue;
            }
            long sum = arr[start]+arr[end];

            if(minimum > Math.min(minimum,Math.abs(arr[t]+sum))) {
                ans[0] = arr[t];
                ans[1] = arr[start];
                ans[2] = arr[end];
                minimum = Math.min(minimum,Math.abs(arr[t]+sum));
            }
            if((arr[t]+sum)>0)
                end--;
            else
                start++;

        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        arr = new long[N];

        for(int i = 0 ; i < N ; i++)
            arr[i] = Integer.parseInt(input[i]);

        Arrays.sort(arr);
        ans = new long[3];
        for (int i = 0 ; i < N ; i++)
            twoPointer(i);

        Arrays.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < 3 ; i++){
            sb.append(ans[i]);
            if(i!=2)
                sb.append(" ");
        }

        System.out.println(sb);
    }
}