문제
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때 (같은 인덱스를 두 번 고르는 것 허용), 두 수의 차이가 M 이상이면서 가장 작은 경우를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)과 M (0 ≤ M ≤ 2,000,000,000)이 주어진다.
다음 N개의 줄에 수열의 각 원소가 주어진다. 각 원소는 절댓값이 2,000,000,000 이하인 정수이다.
출력
두 수의 차이의 최솟값을 출력한다. 항상 답이 존재한다.
예제
입력 1
3 3
1
5
3출력 1
3풀이
핵심 아이디어: 배열을 정렬한 후 두 포인터를 사용하면 O(N) 시간에 조건을 만족하는 최소 차이를 구할 수 있다.
- 배열을 오름차순으로 정렬한다.
- 두 포인터
s(시작)와e(끝)를 모두 0으로 초기화한다. s를 0부터 N-1까지 증가시키면서:arr[e] - arr[s] < M이고e < N-1인 동안e를 증가시킨다.arr[e] - arr[s] >= M이면 현재 차이로 정답을 갱신한다.
e는 단조증가하므로 전체 시간 복잡도는 정렬을 제외하면 O(N)이다.
정렬된 배열에서 e는 뒤로만 이동하므로 불필요한 재탐색이 없다는 점이 핵심이다.
코드
import java.io.*;
import java.util.*;
public class Day354BOJ2230수고르기 {
static int N, M, s, e, tmp, ans = Integer.MAX_VALUE;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr);
for (s = 0; s < N; s++) {
while (e < N - 1 && arr[e] - arr[s] < M)
e++;
if (arr[e] - arr[s] >= M)
ans = Math.min(ans, arr[e] - arr[s]);
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N log N) — 정렬 O(N log N) + 두 포인터 순회 O(N)
- 공간: O(N) — 입력 배열 저장