[BOJ2230] 수 고르기

문제 설명

문제 링크

• 수 배열이 주어지고, 두 수의 차이가 M 이상인 수 조합 중 가장 차이가 적은 조합을 구하는 문제이다.
• 풀이과정이 여러개가 있는 것 같은데 그 중, lowerbound를 떠올려서 해결하였다.

풀이 과정

• 수 배열의 개수인 N이 주어지고, 배열 중 두개의 원소를 선택해서 그 두 원소의 차이가 M 이상인 것 중 가장 최소를 구하는 문제이다.
• 먼저 N개의 수배열을 정렬을 한다. (O(NlogN) 소모)
• 앞에서부터 해당원소(a라고 가정)를 기준으로 a+M보다 크거나 같은 첫번째 인덱스를 lowerbound를 이용하여 구한다.(하나 원소당 O(logN) 소모)
• 전체 원소를 탐색해야하므로 O(NlogN).
• 시간복잡도는 O(NlogN)
• 투포인터를 이용해서도 충분히 풀 수 있을 것 같다. 다음에는 투포인터를 이용해서 추가 풀이를 올려볼 예정.

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

public class BOJ2230_수고르기 {
    static int N, M;
    static int output = Integer.MAX_VALUE;
    static long[] input;
    public static void main(String[] args) 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());
        input = new long[N];
        for (int i = 0; i < N; i++) {
            input[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(input);
        for (int i = 0; i < N; i++) {
            long nextNum = input[i] + M;
            int idx = lowerBound(0, N, nextNum);
            boolean flag = false;
            if (idx != N) {
                flag = true;
                output = (int) Math.min(output, input[idx] - input[i]);
            }
            if (!flag) break;
        }
        System.out.println(output);
    }

    static int lowerBound(int left, int right, long key) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (input[mid] < key) left = mid + 1;
            else right = mid;
        }
        return right;
    }
}