[백준][Java] 2230 - 수 고르기

목차

문제 정보

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

2230번: 수 고르기

난이도 : G5

유형 : 투포인터, 이분탐색

시간 : O(NlogN)

---

문제 풀이

투포인터와 이분탐색을 같이 사용하여 풀이를 했다.

투포인터는 왼쪽, 오른쪽 포인터를 이용하는 개념이다.

 

왼쪽 포인터는 순차적으로 수열의 인덱스로 사용하였고

오른쪽 포인터는 이분탐색으로 얻은 인덱스로 사용하였다.

 

주의할 점은 이분탐색을 하기 전에는 미리 정렬을 해주어야 한다.

---

코드

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

public class Main {

    private int N, M;
    private int[] numbers;
    private int res;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(numbers);

        int left = 0;
        int right = N;
        int mid;
        res = numbers[right - 1] - numbers[left];
        for (int i = 0; i < N; i++) {
            left = i;
            right = N;

            out:
            while (left < right) {
                mid = left + right >> 1;
                if (numbers[mid] - numbers[i] == M) {
                    res = numbers[mid] - numbers[i];
                    break out;
                } else if (numbers[mid] - numbers[i] > M) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            if (right == N) {
                continue;
            }

            res = Math.min(res, numbers[right] - numbers[i]);
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}