문제 풀이/백준
BOJ 2230번: 수 고르기
danbibibi
2023. 9. 3. 17:38
문제
문제 바로가기> BOJ 2230번: 수 고르기
2230번: 수 고르기
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어
www.acmicpc.net
풀이
정렬과 투 포인터를 이용하여 O(nlogn) 안에 문제를 해결할 수 있다.
#include<iostream>
#include<algorithm>
#define MAX 100001
using namespace std;
int N, M;
int num[MAX];
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) cin >> num[i];
}
void solution() {
sort(num, num + N);
int ans = 2000000001, l = 0, r = 1, diff;
while (r < N) {
diff = num[r] - num[l];
if (diff >= M) {
ans = min(ans, diff);
l++;
}
else r++;
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input();
solution();
}