[백준] 2473번 - 세 용액 [Java]

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

 

[백준] 2473번 - 세 용액 [Java]

[백준] 2473번 - 세 용액 [Java]

---

1.  아이디어

 

기존 두 용액 문제에서 용액의 수가 하나 더 늘어난 문제로 반복문 내에서 투 포인터 알고리즘을 돌리는 방식으로 세 용액을 다룰 수 있다.([코딩테스트 준비/백준] - [백준] 2470번 - 두 용액 [Java])

---

2. 문제풀이

 

용액 하나를 고정시키고 투 포인터 알고리즘을 돌리면 세 용액을 다룰 수 있다. 이때 고정시킨 용액을 반복문으로 처리하면 되며 세 용액의 합을 구하는 과정에서 int형 오버플로우가 발생하는 것에 대비해 그냥 long 타입 배열로 관리했다.

---

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        long[] 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);

        long min = Long.MAX_VALUE;
        long[] ans = new long[3];

        for (int i = 0; i < N - 2; i++) {

            int fixed = i;
            int left = i + 1;
            int right = N - 1;

            while (left < right) {
                long sum = arr[fixed] + arr[left] + arr[right];

                if (Math.abs(sum) < min) {
                    min = Math.abs(sum);
                    ans[0] = arr[fixed];
                    ans[1] = arr[left];
                    ans[2] = arr[right];
                } else {
                    if (sum < 0) left++;
                    else right--;
                }
            }
        }

        sb.append(ans[0]).append(" ").append(ans[1]).append(" ").append(ans[2]);

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기