문제 탐색하기

입력 자료 정리

1. n은 전체 용액의 수, 이후 들어오는 n개의 값은 각 용액의 특성값을 의미한다

해결방법 추론

1. 이전 두 용액의 변형 문제다. n이 5000으로 작기 때문에 이중포문까지 가능하다
2. 세 용액을 더한다고 생각하면 int형 범위를 벗어날 수 있다.
   따라서 long 타입을 사용해야한다
3. 두용액 문제는 투포인터로 가능했으나, 여기서는 세가지를 선택해야한다.
   세포인터 같은 것은 없다!
4. n의 범위가 줄어든 것을 생각해서 해결책을 만들면된다
5. n-2까지 탐색하면서 하나를 고정하고,
   그 이후 값들을 기준으로 투포인터 탐색하면 찾을 수 있을 것이다
6. 즉 left 포인터를 고정시켜두고 mid 포인터와 right 포인터로 투포인터 탐색하면서
   최적의 값을 갱신해나간다면 정답을 구할 수 있을 것이다.
7. 투포인터 과정은 이전 두 용액 문제 방식으로 진행한다

시간복잡도 계산

1. 시간복잡도는 O(n^2)이 될 것이다.
   left를 고정하는 과정과 mid와 right를 투포인터 탐색하는 과정에서
   각각 n의 연산이 발생하기 때문이다.

코드 설계하기

입력값 상태 관리

1. 입력값 n은 변수에 저장하고 각 원소값들은 long타입 1차원 배열에 저장한다
2. 투포인터 형식의 탐색을 위해 오름차순 정렬해준다
3. 출력을 위해 사용할 세가지 정답 포인터 변수와
   0에 가까운 차이를 담을 ans 변수를 세 용액의 최대로 합친 3 x 10^9로 초기화한다
   이대 ans는 long타입으로 지정하자

구현 코드 설계

1. n-2전까지 탐색하며, left 포인터를 정하고
   i+1 위치의 mid와 n-1위치의 right인 투 포인터를 초기화한다
2. 투포인터 탐색을 하는데, left와 right는 동일하면 안 되므로
   left < right인 동안 탐색을 지속한다
3. 이동한 두 용액 문제와 동일하게 합산을 구하고 차이도 구해주며,
   차이가 ans보다 작은 경우 세가지 포인터와 ans를 갱신해준다
4. 합산이 0보다 작으면 left를, 크거나 같으면 right를 갱신한다

출력값 설계

1. 완성한 3가지 포인터 위치의 값을 출력하면 정답이 된다.

정답 코드

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);

        int ansL = 0;
        int ansM = 0;
        int ansR = 0;
        long ans = 3_000_000_000L;
        for (int i = 0; i < n-2; i++) {
            int left = i+1;
            int right = n-1;
            while(left < right){
                long sum = arr[i] + arr[left] + arr[right];
                long diff = Math.abs(arr[i] + arr[left] + arr[right]);
                if(ans > diff){
                    ans = diff;
                    ansL = i;
                    ansM = left;
                    ansR = right;
                }

                if(sum < 0){
                    left++;
                }else{
                    right--;
                }
            }
        }

        bw.write(arr[ansL] + " " + arr[ansM] + " " + arr[ansR]);

        br.close();
        bw.close();
    }

}

문제 링크

2473번 - 세 용액