[BOJ 2230] 수 고르기
- 문제풀이
문제
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.
출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- 1 ≤ N ≤ 100,000
- 0 ≤ M ≤ 2,000,000,000
- 0 ≤ |A[i]| ≤ 1,000,000,000
풀이
$N$개의 정수로 이루어진 수열에서 두 수를 선택했을 때, 그 차이가 $M$ 이상이면서 가장 작은 경우를 찾는 문제다.
가장 단순하게 생각하면 모든 두 수의 쌍을 비교하는 방법을 떠올릴 수 있다. 하지만 $N$의 범위는 최대 $100\,000$이다. 이중 반복문으로 모든 쌍을 확인한다면 시간 복잡도는 $O(N^2)$이 되고, 연산 횟수는 약 $100\,000^2 = 10\,000\,000\,000$회에 달해 시간 제한 2초를 초과하게 된다. 따라서 더 효율적인 접근 방법이 필요하다.
수열을 오름차순으로 정렬하면 두 수의 관계를 파악하기 쉬워진다. 정렬된 상태에서는 투 포인터 알고리즘을 활용하여 $O(N)$의 시간 복잡도로 탐색을 마칠 수 있다.
두 개의 포인터 left와 right를 모두 $0$에서 시작하자. 두 포인터가 가리키는 값의 차이를 diff라고 할 때, 다음과 같은 규칙으로 포인터를 이동시킨다.
만약 $diff < M$이라면:
차이가 $M$보다 작으므로, 차이를 더 키워야 한다. 정렬된 배열이므로
right를 오른쪽으로 이동시켜 더 큰 값을 선택하게 한다.만약 $diff \geq M$이라면:
조건을 만족하는 차이를 찾았다. 현재
diff값이 최소 차이인지 확인하고 갱신한다. 더 작은 차이가 가능한지 확인하기 위해left를 오른쪽으로 이동시켜 차이를 줄여본다.
이 과정을 right가 $N$에 도달할 때까지 반복하면 된다. 정렬에 $O(N \log N)$, 투 포인터 탐색에 $O(N)$이 소요되므로 전체 시간 복잡도는 $O(N \log N)$으로 충분히 해결 가능하다. 주의할 점은 $M$의 범위가 $2\,000\,000\,000$까지 가능하므로, 답을 저장할 변수의 초기값을 충분히 크게 설정해야 한다.
소스코드
Github Link : Source Code
참고 알고리즘 : 투 포인터