[백준 - 2470] 두 용액 - Java

문제 설명

 

2470번: 두 용액

 

접근 방법

해당 문제는 투 포인터 알고리즘을 통해 해결할 수 있었습니다.

 

최초 용액 정보를 받은 데이터를 오름차순으로 정렬해줍니다. (내림차순으로 정렬해도 무방합니다.) 이후 오름차순된 해당 데이터 상 시작점과 끝점을 투 포인터로 삼아 두 점의 합을 구하는데, 이 합이 최대한 0에 가까운 경우의 두 용액의 값을 결과값으로 저장하도록 합니다. 이때 시작점과 끝점을 투 포인트로 삼은 이유는 최솟값과 최댓값을 합쳤을 때 0에 가까울 확률이 가장 높기 때문입니다.

 

            int start = 0, end = n - 1, characteristicValue, target = 2000000000;
            characteristicValue = Math.abs(solutions[start] + solutions[end]);
            
            if (target > characteristicValue) {
                target = characteristicValue;
                result[0] = solutions[start];
                result[1] = solutions[end];
                if (target == 0) break;
            }

 

최초 target 변수에 문제에서 발생할 수 있는 두 용액의 합 최댓값을 저장했고 두 용액의 합을 구해 target 값과 비교한 후 target 보다 작으면 결과값으로 저장하고 해당 값이 0이라면 즉시 프로그램을 종료하도록 했습니다.

 

이후 시작점과 끝점 중 하나를 오름차순된 데이터 상 중심 방향으로 이동하도록 조작한다음 다시 합을 구해 이 값이 앞서 구한 것 보다 작은지 검사하고, 작다면 이동한 값으로 결과값 재설정, 크다면 반대쪽 점을 이동하여 두 용액의 합을 target과 비교하도록 했습니다.

 

            if (characteristicValue > Math.abs(solutions[start + 1] + solutions[end])) {
                start++;
            } else {
                end--;
            }

 

이러한 탐색은 최종적으로 시작점과 끝점이 만나기 직전까지(최악의 경우) 반복해줍니다.

 

소스 코드

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

class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] solutions = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(solutions);

        int[] result = new int[2];
        int start = 0, end = n - 1, characteristicValue, target = 2000000000;

        while (start < end) {
            characteristicValue = Math.abs(solutions[start] + solutions[end]);
            if (target > characteristicValue) {
                target = characteristicValue;
                result[0] = solutions[start];
                result[1] = solutions[end];
                if (target == 0) break;
            }

            if (characteristicValue > Math.abs(solutions[start + 1] + solutions[end])) {
                start++;
            } else {
                end--;
            }
        }

        System.out.printf("%d %d", result[0], result[1]);
    }
}

 

참고 자료

• https://www.acmicpc.net/problem/2470