[백준/c++] 2230번: 수 고르기

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

 

문제 요약

 

N개의 정수로 이루어진 수열 A[1] ~ A[N]

이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 가장 작은 경우를 구하라.

 

범위

 

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000 → long long 사용
• 0 ≤ |A[i]| ≤ 1,000,000,000

 

---

 

 

두 수를 고르는 포인터(L, R)를 사용. 

이 문제는 따로 차이 값을 변수에 저장하면서 할 필요 없이 바로 조건문에서 계산해서 해도 된다.

 

L을 첫 번째 수로 두고 R을 뒤로 이동시키면서 차이 값을 계산해서 만약 m보다 작다면 계속 뒤로 이동하도록 했다.

여기서 중요한 것은 정렬을 해준 것이다. 입력된 배열이 정렬되어 있으면, R과 L의 차이점이 처음으로 나왔을 때 그 값이 바로 m 이상인 최소 차이 값이므로 ans에 넣어준 뒤(최솟값 비교 후) 다음 L로 넘어가면 된다. 차이값이 점차 커질 것이므로 다음 값들은 볼 필요가 없다.

 

 

#include <iostream>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
int n, A[100001];
ll m;

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> A[i];
}

void solution(){
    sort(A, A+n);
    int R = 0;
    ll ans = 2000000001;
    for(int L=0; L<n; L++){
        while(R+1 < n && A[R] - A[L] < m) ++R;
        if (A[R] - A[L] >= m) ans = ans > A[R] - A[L] ? (A[R] - A[L]) : ans; //최소 구하기
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

최솟값을 비교해서 ans에 넣어줘야 하는데 깜박하고 넣지 않아서 틀렸던 문제 😱

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!