백준 2230) 수 고르기 골드 5 투 포인터

 

풀이:  가장 중요한 부분은 투 포인터 알고리즘을 활용하여 해결 하는 것입니다.

 

n이 100,000까지니까 시간 복잡도 O(n 제곱)은 당연히 안될꺼라는 것을 아실겁니다.

 

투 포인터로 빠르고 간단하게 순회하기 위해서 vector에 값을 입력받고 오름차순 정렬 시켜주면 됩니다. 

 

그리고 투 포인터의 while 조건이 중요합니다 ->  while(i < n && j < n && i <= j)
 

당연히 i와 j는 n을 넘어가면 OutOfBounds 뜰 것 입니다. i가 j보다 커지는 것은 마이너스로 가기 때문에 m은 0 이상 값만

 

들어오니 i가 j를 넘어서는 상황은 고려하지 않습니다

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    long long n,m;

    cin >> n >> m;

    vector<long long> dp(n);

    long long mins = 20000000000;


    for(int i = 0; i < n; i++) {
        cin >> dp[i];
    }

    sort(dp.begin(), dp.end());

    int i = 0;
    int j = 1;

    while(i < n && j < n && i <= j) {
        if(dp[j] - dp[i] >= m) {
            mins = min(mins, dp[j] - dp[i]);
            i++;
        }
        else {
            j++;
        }
    }


    cout << mins;


}