문제 탐색하기

입력 자료 정리

1. n은 용액의 개수를 의미한다
2. 이어서 들어오는 n개의 값은 각 용액의 특성값을 의미한다

해결방법 추론

1. 이전 두 용액문제를 변형한 문제다.
2. 다만 이전에는 두 용액만 더하는 문제였다면 이번에는 세용액을 더하는 문제다
3. n의 입력값이 5000이라 두 용액만 더한다면 브루트포스로 가능할 것 같은데
   세 용액을 더하는 문제라 브루트포스 만으로는 불가능하다
4. 그렇다면 투포인터랑 브루트포스를 섞어서 활용한다면? 입력값을 5000으로 준 것이 이렇게 활요해서 풀라는게 아닌가 생각이 들었다
5. 맨 왼쪽을 n-2만큼 탐색하면서 고정시켜두고, 중간과 오른쪽을 투포인터로 푼다면 시간제한안에 풀 수 있을 것이다
6. 각 투포인터마다 절댓값 합산을 구해서 0에 가까운 값으로 갱신하고,
   단순 합산으로 0보다 작을 경우 left를 늘리고 반대의 경우 right를 줄인다면 정답을 찾아갈 수 있을 것이다

시간복잡도 계산

1. 시간복잡도는 탐색에서 n-2연산, 투포인터에서 n의 연산이 발생한다
   따라서 시간복잡도는 O(n^2)이 된다
2. n의 최대는 5000이므로 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n값은 int형 변수에 관리한다
2. 입력값은 long타입 1차원 배열에서 관리하며, 오름차순으로 투포인터 탐색을 할 수 있도록 준비한다
3. 입력값 배열의 값들은 int형 범위안에 들어오긴 하는데, 합산하는 과정에서 int형 범위를 벗어나면 오버플로우가 발생한다. 따라서 long타입으로 선언해야한다
4. 정답을 위한 left, mid, right 위치 변수를 선언한다.
5. 0에 가까운 수를 찾기 위해 가장 큰 값인 3_000_000_000L을 long타입 ans변수에 초기화한다

구현 코드 설계

1. n-2만큼 탐색하면서 left와 right를 각각 i+1과 n-1로선언한다.
   i는 세 용액중 left, left와 right는 mid와 right를 의미한다
2. left와 right는 같을 수 없으므로 left < right인동안 투포인터 탐색을 진행한다
3. 합산과 절댓값 차이를 구해서 ans와 diff 변수에 보관한다
4. diff가 ans보다 작으면 0에 더 가까운 값이므로 ans와 정답을 위한 left,mid,right를 갱신한다
5. 이어서 단순 합산을 비교해서 0보다 작으면 음수 용액이 더 크다는 것이므로 left를 늘리고
   반대는 right를 줄이며 탐색을 이어나간다

출력값 설계

1.완성한 left, mid, right 위치의 배열값을 출력하면 정답이 된다.

정답 코드

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 leftAns = 0;
        int rightAns = 0;
        int midAns = 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[left] + arr[right] + arr[i];
                long diff = Math.abs(arr[left] + arr[right] + arr[i]);
                if(diff < ans){
                    ans = diff;
                    leftAns = i;
                    rightAns = right;
                    midAns = left;
                }

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

        bw.write(arr[leftAns] + " " + arr[midAns] + " " + arr[rightAns]);


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

}

문제 링크

2473번 - 세 용액