[BaekJoon] 2473 세 용액 (Java)

1.  문제 링크

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

2.  문제

요약

• 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있는데, 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있습니다.
• 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타냅니다.
• 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의하는데, 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만드려고 합니다.
• 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있습니다.
• 산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 5,000보다 작거나 같은 전체 용액의 수 N이 주어지고 두 번째 줄에 용액의 특성값을 나타내는 N개의 정수가 주어집니다.
  • 용액의 특성값은 모두 -1,000,000,000 이상 1,000,000,000 이하이고 N개의 용액들의 특성값은 모두 다르며, 산성 용액으로만 혹은 알칼리성 용액으로만으로 입력이 주어지는 경우도 있을 수 있습니다.
• 출력: 첫 번째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을 출력합니다. 세 용액은 특성값의 오름차순으로 출력합니다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무거나 하나를 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static long answer;
    static int[] solutions, result;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        solutions = new int[N];
        for(int idx = 0; idx < N; idx++) solutions[idx] = scanner.nextInt();
    }

    static void solution() {
        Arrays.sort(solutions);
        result = new int[3];
        answer = Long.MAX_VALUE;
        for(int idx = 0; idx < N; idx++) twoPointer(solutions, idx);
        Arrays.sort(result);
        for(int r : result) sb.append(r).append(' ');
        System.out.println(sb);
    }

    static void twoPointer(int[] solutions, int idx) {
        int left = 0, right = N - 1;
        if(idx == 0) left = 1;
        if(idx == N - 1) right = N - 2;
        while(left < right) {
            long sum = (long)solutions[left] + solutions[right] + solutions[idx];
            if(answer > Math.abs(sum)) {
                answer = Math.abs(sum);
                result[0] = solutions[left];
                result[1] = solutions[idx];
                result[2] = solutions[right];
            }
            if(sum >= 0) {
                right--;
                if(idx == right) right--;
            } else {
                left++;
                if(idx == left) left++;
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 용액들을 각각 세 용액 중 하나의 용액으로 선택하여 해당 용액과 다른 두 용액을 합쳐서 0에 가장 가까운 용액을 만듭니다. 그 중 가장 0에 가까운 세 용액을 구합니다.
• 하나의 용액을 선택했을 때, 나머지 두 용액은 투포인터를 통해 구합니다.
  • 우선 투포인터 알고리즘을 수행하기 위해 주어진 용액을 용액의 특성값에 대한 오름차순으로 정렬합니다.
  • 각 용액을 기준으로 투포인터 알고리즘을 통해 다른 두 용액을 고릅니다.
  • 투포인터 알고리즘 수행 시에 왼쪽 포인터와 오른쪽 포인터를 정해야 하는데,
    • 만약 선택한 한 용액이 처음 용액이라면 왼쪽 포인터는 두 번째, 오른쪽 포인터는 마지막으로 설정하여 시작하고
    • 선택한 한 용액이 마지막 용액이라면 왼쪽 포인터는 첫 번째, 오른쪽 포인터는 마지막에서 두 번째로 설정하여 시작하며
    • 두 경우 모두 아니라면 왼쪽 포인터는 첫 번째, 오른쪽 포인터는 마지막으로 설정하여 시작합니다.
  • 왼쪽 포인터에 해당하는 용액과 오른쪽 포인터에 해당하는 용액, 처음에 고른 용액의 특성값을 합하여 그 합이 0보다 크거나 같다면 합을 줄이기 위해 오른쪽 포인터를 하나 줄이고 0보다 작다면 합을 늘리기 위해 왼쪽 포인터를 하나 늘립니다.
    • 이 때, 이 합의 절댓값이 이전에 합이 가장 0에 가까운 세 용액의 합의 절댓값보다 작다면 세 용액과 합을 갱신합니다.
  • 위 과정을 모든 용액에 대해 수행해보고 답을 도출합니다.