[알고리즘] 2470. 두 용액

package org.example.알고리즘.두용액;

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

/**
 * packageName    : org.example.알고리즘.두용액
 * fileName       : Main
 * author         : ipeac
 * date           : 2024-03-17
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2024-03-17        ipeac       최초 생성
 */
public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");
            
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(input[i]);
            }
            
            Arrays.sort(arr);
            
            int left = 0;
            int right = N - 1;
            int min = Integer.MAX_VALUE;
            int resultLeft = 0;
            int resultRight = 0;
            
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (Math.abs(sum) < min) {
                    min = Math.abs(sum);
                    resultLeft = arr[left];
                    resultRight = arr[right];
                }
                
                if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
            
            System.out.println(resultLeft + " " + resultRight);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

• 투 포인터 & 이분탐색 문제이다
  - 왼쪽부터 오른쪽으로 일반적인 투포인터 문제와 동일하게 합계가 음수인 경우 왼쪽 포인터를 양수쪽으로
  • 함계가 양수인 경우 오른쪽 포인터를 음수쪽으로 당겨가며 0가 근접한 값을 resultLeft 와 resultRight 에 담으면 된다.
• 이분 탐색류는 항상 정렬되어 있어야한다는 것을 잊으면 안된다.
• 그리고 시간복잡도는
  - O(log n)
  • 탐색대상인 n 개 배열에서 매번 탐색마다 탐색 범위를 절반으로 줄여나가기 때문이다.