Algorithm/투포인터
백준 2230 수고르기 c++ // 투포인터 사용방법
Mini_96
2023. 11. 6. 11:06
https://www.acmicpc.net/problem/2230
2230번: 수 고르기
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어
www.acmicpc.net
1. 의사코드
/*
* 투포인터
* 1.정렬
* 2.for(st=0~n)
* 3. while(en범위쳌 && 조건만족안하면) en++
* 4. 정답갱신
*/
en을 1칸씩 우측으로 옮겨가면서 탐색한다.
2. 전체코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100004];
int ret = 0x7fffffff;
/*
* 투포인터
* 1.정렬
* 2.for(st=0~n)
* 3. while(en범위쳌 && 조건만족안하면) en++
* 4. 정답갱신
*/
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
int en = 0;
for (int st = 0; st < n; ++st) {
while (en < n && a[en] - a[st] < m) en++;
if (en == n) break; //범위쳌
ret = min(ret, a[en] - a[st]);
}
cout << ret;
}