백준 알고리즘 2230번 : 수 고르기

링크

https://www.acmicpc.net/problem/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이상인 두 수를 고를 수 있다.

예제 입력 및 출력

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tiii = tuple<int,int,int>;

const int INF = 0x7fffffff;

int main() {
	fastio;
  int n,m; cin >> n >> m;
  vi v(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  sort(v.begin(), v.end());
  int en = 0,ans = INF;
  for(int st = 0; st < n; st++){
    while(en < n && v[en] - v[st] < m) en++;
    if(en == n) break;
    ans = min(ans,v[en] - v[st]);
  }
  cout << ans << "\n";
  return 0;
}

두 포인터인 st,en을 증가시키면서 v[en] - v[st]의 값이 m이상일때 갱신해주면 됩니다.