(C++) 백준 2230번 - 수 고르기

문제 링크 : https://www.acmicpc.net/problem/2230 

2230번: 수 고르기

문제 풀이

투 포인터를 사용하여 풀이할 수 있다.

여기서는 st와 en 두 개의 포인터를 사용한다.

1. 배열 A를 입력받은 후, 정렬을 한다.

2. en을 1씩 증가시키면서 A[en] - A[st]의 값이 M 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다.

만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break 한다.

3. st를 1만큼 증가시키고, 다시 과정을 반복한다.

아래 코드는 위 과정을 구현한 것이다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int A[100002];
int st, en;
int mn = 0x7fffffff;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> M >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    sort(A, A+N);
    for(; st < N; st++){
        while(en < N and A[en] - A[st] < M) en++;
        if(en == N) break;
        mn = min(mn, A[en] - A[st]);
    }
    cout << mn;
}