[Baekjoon Online Judge] 2230. 수 고르기 (C++, Java)

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

핵심

N은 최대 100,000

모든 두 원소의 차를 비교하려면 시간복잡도가 O(N^2)이다. (시간초과)

한 원소에 대해 조건에 맞는(차가 M 이상이면서 가장 작은) 원소를 빠르게 찾을 수 있다면, 시간복잡도를 줄일 수 있다.

방법 1. 이분 탐색

A[i] + M에 대한 Lower Bound는 위 조건에 맞는 원소의 인덱스와 동일하다.

이를 모든 i에 대해 찾고 차를 비교하면 된다.

시간복잡도는 O(NlogN)

방법 2. 투 포인터 알고리즘

1. 정렬 후 두 개의 포인터를 시작 지점에 둔다. (i = 0, j = 0)

2. 두 원소의 차가 M보다 커지는 지점까지 j를 옮긴다.

3. 차가 지금까지의 차 중에서 가장 작다면, 갱신한다.

4. i를 1증가 시키고 2~3을 반복한다.

시간복잡도는 O(N+logN)

Code (C++) with Two Pointer Algorithm

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000

int n, m;
int arr[MAX_N];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr + n);

	int i = 0, j = 1, min_diff = 0x7fffffff;
	while (i < n && j < n) {
		int diff = arr[j] - arr[i];
		if (diff == m) {
			cout << m;
			return 0;
		}
		else if (diff > m) {
			min_diff = min(min_diff, diff);
			i++;
		}
		else
			j++;
	}
	cout << min_diff;
}

 

Code (Java) with Binary Search

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int idx = lowerBound(arr, arr[i] + M);
            if (idx < N) {
                int diff = arr[idx] - arr[i];
                ans = Math.min(ans, diff);
            }
        }

        System.out.println(ans);
    }

    public static int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}