[BOJ] 2473: 세 용액(Java)

문제 링크

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

2473번: 세 용액

---

💡 풀이

이전에 해결했던 두 용액과 매우 유사한 문제입니다. 단지, 섞는 용액의 개수가 1개가 추가된 문제입니다. 두 용액 문제의 풀이는 여기서 확인할 수 있습니다. 

Two Pointer

두 포인터를 사용해서 문제를 풀이합니다. 남은 용액 중 가장 작은 원소를 가리키는 left와 가장 큰 원소를 가리키는 right를 사용하는데, 세 용액의 합을 구하기 때문에 mid를 추가합니다. 

이 세 용액에 대해 검사하기 위해, left를 0부터 N(전체 용액의 개수) - 2까지 진행시키며, mid를 left + 1로 설정하고, mid 와 right에 대해 Two Pointer를 적용시키며 풀이하면 됩니다. (이 과정에 대한 자세한 풀이는 두 용액 링크에서 확인할 수 있습니다.)

 

전체 코드

전체적인 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q2473 {
    static int N;
    static long[] solutions;
    static long diff = Long.MAX_VALUE; // 0과의 차이
    static long[] answer = new long[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        solutions = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            solutions[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(solutions);

        for (int left = 0; left < N - 2; left++) {
            int mid = left + 1;
            int right = N - 1;
            while (mid < right) {
                long sum = solutions[left] + solutions[mid] + solutions[right];

                if (Math.abs(sum) < diff) {
                    diff = Math.abs(sum);
                    answer[0] = solutions[left];
                    answer[1] = solutions[mid];
                    answer[2] = solutions[right];
                }

                if (sum > 0) {
                    right--;
                } else {
                    mid++;
                }
            }
        }

        System.out.println(answer[0] + " " + answer[1] + " " + answer[2]);
    }
}