[백준] 2473번 세 용액

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   많은 종류의 산성 용액과 알칼리성 용액이 있을 때, 이 중에서 같은 양으로 혼합하여 특성값이 0에 가장 가까운 세 용액을 찾는 문제이다. 예를 들면, 주어진 용액이 [-2, 6, -97, -6, 98]인 경우 특성값이 -97와 -2, 98인 용액을 혼합하면 특성값 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다.

   첫째 줄에 전체 용액의 수 N이 주어지고, 둘째 줄에 용액의 특성값을 나타내는 N개의 정수가 빈칸으로 구분되어 주어진다. 제한 사항은 다음과 같다.

 

• 3 ≤ N ≤ 5,000
• -1,000,000,000 ≤ 특성값 ≤ 1,000,000,000
• 특성값은 모두 다르다.
• 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
• 세 용액의 특성값은 오름차순으로 출력하고, 답이 2개 이상인 경우 그 중 아무거나 하나를 출력한다.
• 세 용액은 서로 다르다.

 

 

 

---

접근 방식

   투 포인터의 개념을 이용해 문제를 해결하였다. 문제의 핵심은 하나의 용액을 선택한 뒤, 선택한 용액의 우측 범위에서 투 포인터를 이용해 나머지 2개의 용액을 선택하는 것이다.

   다음과 같이 예제가 주어졌을 때, 정렬 후 가장 좌측에 있는 용액을 선택한다.

 

 

   하나의 용액이 선택되었으면 중복 탐색을 방지하기 위해 선택한 용액의 우측 범위에서 left, right를 정해 0에 가까운 경우를 갱신해 나간다. 만약 sum이 음수면 0에 가깝게 하기 위해 left를 증가시키고, sum이 양수면 0에 가깝게 하기 위해 right를 감소시킨다.(오름차순으로 정렬되어있기 때문에 좌측으로 갈수록 더 낮은 값이, 우측으로 갈수록 더 높은 값이 위치한다.)

 

 

   이전의 합이 음수였기 때문에 left를 증가시킨다. 하지만 -2와 2는 절댓값이 같기 때문에 갱신은 발생하지 않는다.

 

 

   이전 합이 양수였기 때문에 right를 감소시킨다. 합은 -90이기 때문에 갱신이 발생하지 않는다. 이 다음의 경우 합이 음수이기 때문에 left가 증가하며 right와 같은 위치에 존재하게 되어 투 포인터 연산이 종료된다. 이 후엔 선택했던 용액의 위치를 증가시킨 뒤 이전 과정을 반복한다. 전체 연산이 끝나면 최종적으로 0에 가장 가까운 값은 -2이며, 이때의 결과는 '-98 -2 98'이 된다.

 

 

※ 세 가지 용액을 더할 때 int 범위를 초과하여 오버플로우가 발생할 수 있다.

※ 아래 코드에선 용액이 치우쳐서 들어온 경우(산성 용액만 or 알칼리성 용액만), input을 정렬 후 한 쪽의 3가지 용액을 바로 출력하였다.

---

코드

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

public class 백준2473번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] input = new int[N];
        boolean[] flag = new boolean[2];

        token = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(token.nextToken());
            if (input[i] < 0) flag[0] = true;
            else if (input[i] > 0) flag[1] = true;
        }
        Arrays.sort(input);

        //산성용액만 있거나 알칼리성 용액만 있는 경우 한 쪽에서 3를 뽑아 출력 및 종료
        if (!(flag[0] & flag[1])) {
            int i = (flag[0] ? N : 3);
            System.out.println(input[i - 3] + " " + input[i - 2] + " " + input[i - 1]);
            return;
        }

        int[] save = new int[3];
        int left = 0, right = 0;
        long sum = 0, min = Long.MAX_VALUE;

        //반복문 앞에 명칭을 선언하면 break로 해당 반복문을 종료 가능
        loop:for (int i = 0; i < N - 2; i++) {
            //특정 용액 선택 후 우측 범위에서 2가지 용액을 투 포인터 방식으로 탐색
            left = i + 1;
            right = N - 1;
            while (left < right) {
                //만들어진 용액의 특성값
                sum = input[i] + input[left] + input[right];
                //특성값의 절댓값이 이전에 저장된 min(0에 가까운 정도)보다 작으면 갱신
                if (Math.abs(sum) < Math.abs(min)) {
                    min = sum;
                    save[0] = input[i];
                    save[1] = input[left];
                    save[2] = input[right];
                }
                //특성값이 0인 경우 바로 종료
                if (sum == 0) break loop;
                //sum이 음수인 경우 0에 가깝게 만들기 위해 left 증가
                else if (sum < 0) left++;
                //sum이 양수인 경우 0에 가깝게 만들기 위해 right 증가
                else right--;
            }
        }
        System.out.println(save[0] + " " + save[1] + " " + save[2]);
    }
}