[백준] 수 고르기(2230)

문제 링크 : [백준] 수 고르기(2230)

문제 설명

수열이 주어졌을 때, 수열에서 두 수를 골랐을 때, 두 값의 차이 중, M 이상이 되는 값 중 최소가 되는 값을 출력하세요.

입력

N(수열의 크기, 1 <= N <= 100,000)
D_i(0<= |D_i| <=1,000,000,000)

3 3
1
5
3

출력

자르는 전깃줄 수와 자르는 전깃줄 위치(오름차순)

4

카테고리

#정렬 #투포인터

시간 복잡도 상한

O(N)

해결 방법

1. 모든 경우를 조사하면 가능하나 TLE가 됩니다.
2. 값이 정렬 되어있다면, 두 수의 간격이 멀어진다면 차이는 커지고, 두 수의 간격이 좁아진다면 차이는 줄어들게 됩니다.
3. 그래서 먼저 데이터를 정렬해야 합니다.
4. 정렬이 되어있다면, 한 위치를 기준으로 다른 위치의 차이와의 차이가 M보다 작다면 차이를 늘려야하기 때문에, 오른쪽 위치를 한칸 늘립니다.
5. 반대로 M보다 크다면 왼쪽 값을 오른쪽으로 옮겨 두 위치의 차이를 좁혀 차이를 작아지게 합니다.
6. 그러면서 차이를 M 이상인 것들 중 최대값을 구합니다.
7. 시간복잡도는 2N정도가 됩니다.

시간복잡도

O(N)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,d[100000],l,r,a=2000000001;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(l=0;l<n;l++)cin>>d[l];
    l=0;
    sort(d,d+n);
    while(r<n){
        if(d[r]-d[l]<m)r++;
        else a=min(a,d[r]-d[l]),l++;
    }
    cout<<(n==1?0:a);
}