[백준] 두 용액 (2470번)

문제 이해

• 주어진 배열에서 두 수를 선택해 합이 0에 가장 가까운 쌍을 찾는 문제입니다.
• 배열을 정렬한 후 투 포인터(Two-pointer) 알고리즘을 사용해 빠르게 해결합니다.
• 목표는 합이 0에 가장 가까운 두 수를 찾아 그들의 값과 합의 절댓값을 출력하는 것입니다.

 

핵심 아이디어

1. 투 포인터 알고리즘:
   • 정렬된 배열에서 양 끝에서 출발하는 두 포인터(s, e)를 사용합니다.
   • 왼쪽 포인터(s)는 작은 수를, 오른쪽 포인터(e)는 큰 수를 가리킵니다.
   • 합이 0에 가까워질 수 있도록 절댓값이 큰 수 쪽의 포인터를 이동합니다.
2. 정렬 후 탐색:
   • 배열을 정렬하면 작은 수와 큰 수를 효율적으로 비교할 수 있습니다.
   • 정렬된 배열을 이용하면 한 번의 탐색으로 최적의 답을 찾을 수 있습니다.
3. 합의 절댓값 갱신:
   • 합이 더 작을 때마다 최소 차이와 해당 두 수를 갱신합니다.
   • 이 과정을 반복해 합이 0에 가장 가까운 두 수를 찾습니다.

 

알고리즘 흐름

1. 입력 받기: 배열의 크기와 요소를 입력받아 정수 배열로 변환합니다.
2. 배열 정렬: 투 포인터 탐색을 위해 배열을 오름차순으로 정렬합니다.
3. 투 포인터 탐색:
   • 포인터가 겹칠 때까지 탐색하며, 합의 절댓값이 최소인 경우를 찾습니다.
   • 절댓값이 큰 쪽의 포인터를 이동해 탐색 범위를 좁혀갑니다.
4. 결과 출력: 가장 0에 가까운 합을 만드는 두 수와 그 합의 절댓값을 출력합니다.

---

정답은 더보기 클릭

import java.util.*; // 유틸리티 클래스 사용

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성

        int n = in.nextInt(); // 입력 받을 배열의 크기
        in.nextLine(); // 줄바꿈 문자 소비

        // 입력받은 문자열을 공백 기준으로 나눠 리스트로 변환
        List<String> list = new ArrayList<>(Arrays.asList(in.nextLine().split(" ")));

        // 리스트의 요소를 정수 배열로 변환
        int[] arr = list.stream()
                .mapToInt(Integer::parseInt)
                .toArray();

        // 배열 정렬 (투 포인터를 사용하기 위해)
        Arrays.sort(arr);

        int s = 0;           // 시작 포인터 (배열의 맨 앞)
        int e = n - 1;       // 끝 포인터 (배열의 맨 끝)

        // 초기값 설정: 최소와 최대 값을 배열의 양 끝 값으로 설정
        int min = arr[s];    
        int max = arr[e];    
        int diff = Math.abs(min + max); // 두 수의 합의 절댓값(초기 차이)

        // 투 포인터 탐색 시작
        while (s < e) {
            // 현재 두 수의 합의 절댓값이 기존 최소 차이보다 작으면 갱신
            if (diff > Math.abs(arr[s] + arr[e])) {
                diff = Math.abs(arr[s] + arr[e]); // 차이 갱신
                min = arr[s]; // 최소값 갱신
                max = arr[e]; // 최대값 갱신
            }

            // 절댓값이 큰 쪽의 포인터를 이동시켜 합을 0에 가깝게 만듦
            if (Math.abs(arr[s]) < Math.abs(arr[e])) {
                e--; // 끝 포인터 왼쪽으로 이동
            } else {
                s++; // 시작 포인터 오른쪽으로 이동
            }
        }

        // 결과 출력: 가장 0에 가까운 합을 만드는 두 수와 그 합의 절댓값
        System.out.println(min + " " + max);
    }
}