백준 2467번 용액 - 이분탐색, 투포인터

용액

풀어보자고 ㅋㅋ

 

간단한 이분탐색 문제로 보인다.

두 용액을 선택하여 더한 값이 0과 가깝게 만들어주는 문제이다.

 

다만 양수로만 주어지기도 하고, 음수로만 주어지기도 해서 조건을 조금 넣어줬다.

오랜만에 이분탐색 푸니까 갱신하는 위치를 잘못잡아 시간을 조금 잡아먹었다 그래두 20분컷.. 꼴꼴

 

앞서 말한 조건을 위해 input을 받으면서 최소값과 최대값을 입력받아준다.

변수명은 각각 min, max로 지정.

-99 -41 -14 -8 -4 -1 0

이런식의 입력이 주어진다면 max = 0, if(max <= 0 ) == true일테고

저장된 배열의 끝 인덱스의 두 조합이 가장 0과 가깝겠다.

▶ -1 0 출력

1, 4, 11, 123, 200

이런식의 양수 입력이라면 min = 200,   if(min >= 0 ) == true일테고

저장된 배열의 가장 앞 인덱스 두 조합이 가장 0과 가깝겠다.

▶ 1 4 출력

 

간단한 조건을 넣어주었고 사실 안넣어줘도 이분탐색으로 충분히 찾아낼 수 있다.

또한 정렬된 배열이기에 투 포인터를 활용해서 좌우로 좁혀가는 방식도 가능하다.

 

🔽 이분탐색 코드 

 

import java.io.*;
import java.util.*;
 
public class Main { // 용액
    public static int N;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
 
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
 
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }
 
        if (max <= 0) {
            sb.append(arr[N - 2]).append(" ").append(arr[N - 1]);
        } else if (min >= 0) {
            sb.append(arr[0]).append(" ").append(arr[1]);
        } else { // 이분 탐색으로 서칭
            int mid = 0;
            int now = 0;
            int mini = Integer.MAX_VALUE;
            int idx1 = 0, idx2 = 0;
 
            for (int i = 0; i < N; i++) {
                int low = i + 1;
                int high = N - 1;
 
                while (low <= high) {
                    mid = (low + high) / 2;
                    now = Math.abs(arr[i] + arr[mid]);
 
                    if (mini > now) { // 최솟값 갱신
                        mini = now;
                        idx1 = i;
                        idx2 = mid;
                    }
 
                    if (arr[i] + arr[mid] > 0) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
            }
            sb.append(arr[idx1]).append(" ").append(arr[idx2]);
        }
 
        System.out.println(sb);
    }
}
 

 

🔽 투 포인터 코드

 

import java.io.*;
import java.util.*;
 
public class Main { // 용액
    public static int N;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int left = 0;
        int right = N - 1;
        int mini = Integer.MAX_VALUE;
        int idx1 = 0, idx2 = 0;
 
        while (left < right) {
            int sum = arr[left] + arr[right];
 
            if (Math.abs(sum) < mini) {
                mini = Math.abs(sum);
                idx1 = left;
                idx2 = right;
            }
 
            if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
 
        sb.append(arr[idx1]).append(" ").append(arr[idx2]);
        System.out.println(sb);
    }
}