[백준 / Java] 2467 용액

문제

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

 

 

문제 개요

산성 용액(양수)과 알칼리성 용액(음수)이 주어졌을 때, 두 개의 용액을 혼합하여 특성값이 0에 가장 가까운 조합을 찾는 문제입니다. 두 용액의 특성값을 더한 값이 0에 가까울수록 좋은 조합이며, 이를 만족하는 두 용액을 오름차순으로 출력해야 합니다. 용액들의 특성값은 정렬된 상태로 주어지므로, 이를 활용하여 효율적인 탐색이 가능합니다.

 

 

문제 접근 방법

이 문제는 "두 수의 합이 특정 값에 가장 가까운 쌍을 찾는 문제"로, 투 포인터(Two Pointer) 알고리즘을 활용하여 해결할 수 있습니다.

해결 방법

1. 투 포인터 사용
   • 입력된 용액 배열이 오름차순 정렬된 상태이므로, 양 끝에서 시작하는 두 개의 포인터(left, right)를 활용합니다.
   • left는 가장 작은 값을 가리키고, right는 가장 큰 값을 가리킵니다.
2. 특성값의 합을 계산하면서 탐색
   • sum = arr[left] + arr[right]를 계산합니다.
   • sum이 0에 가까운 값이라면, 현재까지 찾은 최적의 조합을 갱신합니다.
   • 만약 sum > 0이면, 특성값이 너무 크므로 right 포인터를 줄여 작은 값으로 이동합니다.
   • 반대로 sum < 0이면, 특성값이 너무 작으므로 left 포인터를 증가시켜 큰 값으로 이동합니다.
3. 최적의 조합 출력
   • 탐색이 끝나면, 가장 0에 가까운 조합을 출력합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        init();
        search();
    }

    public static void search() {
        int left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE;
        int first = 0;
        int second = 0;

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

            if(Math.abs(sum) < min) {
                min = Math.abs(sum);
                first = arr[left];
                second = arr[right];
            }

            if(sum > 0) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(first + " " + second);
    }

    public static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }
}