[BOJ 2470] 두 용액 (java, 이진탐색)

 

 

 

 

---

문제 링크

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

2470번: 두 용액

---

풀이

반복문을 통해 left = 1 ~ N 까지 조회할 때

- arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함

- N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능

- 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐

 

투 포인터로 풀 경우 좀 더 쉽게 풀이 가능

 

주어진 배열을 오름차순 정렬 했을 때

1	2	3	4	5
-99	-2	-1	4	98

 

 

실수1. Arrays.sort(arr, fromIndex, toIndex) 

(0번 비우고 1번부터 입력) 1 ~ N 인덱스에 대해 정렬 수행해야 하는데 toIndex 가 exclusive(제외) 인지 모르고 실수

Arrays.sort(A, 1, N + 1); 

doc 확인

 

실수2. 이진탐색 초기값 설정 

범위 탐색시 int result 초기값 설정을 이해하지 못하여 시간 소모

직접 손으로 해보기
-99 의 경우 result = 6 리턴됨
-2 의 경우 result = 4 리턴됨

 

실수3. 이진탐색 방향 설정

"-A[left] 이상이 되는 수 중에 가장 왼쪽 값을 찾는다"

---

import java.util.*;
import java.io.*;

public class BOJ2470 {

    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] A;

    static void input() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        A = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) A[i] = Integer.parseInt(st.nextToken());
    }

    static int binarySearch(int[] arr, int L, int R, int target) {
        int result = R + 1;
        while(L <= R) {
            int mid = (L + R) / 2;
            if(target <= arr[mid]) {
                R = mid - 1;
                result = mid;
            } else {
                L = mid + 1;
            }
        }

        return result;
    }

    static void pro() {
        Arrays.sort(A, 1, N + 1);

        int bestValue = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        for(int left = 1; left <= N; left++) {
            // -A[left] 이상인 수 중에 가장 왼쪽 인덱스 반환
            int result = binarySearch(A, left + 1, N, -A[left]);

            if(left + 1 <= result && result <= N && Math.abs(A[left] + A[result]) < bestValue) {
                v1 = A[left];
                v2 = A[result];
                bestValue = Math.abs(A[left] + A[result]);
            }

            if(left +1 <= result - 1 && result - 1 <= N && Math.abs(A[left] + A[result - 1]) < bestValue) {
                v1 = A[left];
                v2 = A[result - 1];
                bestValue = Math.abs(A[left] + A[result - 1]);
            }
        }

        sb.append(v1).append(" ").append(v2);
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}