baekjoon 2230:수 고르기

baekjoon 2230 수 고르기

2230번 수 고르기

접근

모든 경우의 수를 모두 계산하기 위해선 nC2의 횟수가 필요하기 때문에 너무 오래걸린다. 그래서 수 들을 일단 먼저 정렬 시킨후에, two-pointer 방식으로 앞에서부터 차가 너무 작으면 뒤를 늘리고
차가 너무 크면 앞을 늘리고 이런 방식으로 전체를 스캔해들어 간다.
그 숫자들을 또 정렬하기 귀찮아서 map을 이용해서 자동으로 정렬시킨 후 map의 첫번째 원소를 답으로 제출하는 방식으로 했다.

코드

//2230
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  vector<int> v(n, 0);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  // for(auto i : v){
  //   cout << i << " ";
  // }
  int front = 0; int back = 0;
  map<int, int> ans;
  while(true){
    if(back == n || front == n){
      break;
    }
    if(v[back] - v[front] >= m){
      ans[v[back] - v[front]] = 0; //map의 first만 중요하기 때문에 이렇게 했다.
      front++;
    }
    else if(v[back] - v[front] < m){
      back++;
    }
  }
  auto itr = ans.begin();
  cout << itr->first << "\n";
  return 0;
}

배운 점