[BaekJoon 2230번] 수 고르기(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

2230번: 수 고르기

[문제 설명]

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

[입력]

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

[출력]

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

[제한]

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

[입출력 예]

입력	출력
3 3 1 5 3	4

[문제 풀이]

이 문제를 풀 때 직관적으로 떠올릴 수 있는 풀이는 2중 for문을 사용하는 방법이다.
하지만 이 방법의 경우 주어진 범위가 10만이고, O(N^2)의 시간 복잡도를 갖고 있기 때문에 시간초과가 발생한다.

그렇다면, 어떻게 풀어야할까?
바로, 투 포인터 알고리즘을 사용해야 한다.
(관련해선 따로 포스팅을 하도록 하겠다.)

사용했던 방법은 시간 복잡도가 O(N)인 방법이다.
1. 배열을 정렬한다.
2. start와 end 변수를 처음 인덱스에 둔다.
3. 각 인덱스 차이 값이 M보다 작으면 end 값을 증가시켜 준다.
하지만 인덱스 차이 값이 M보다 크거나 같으면 두 값의 차이를 갱신한다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

#include <bits/stdc++.h>
using namespace std;
vector<int> gNumber;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        gNumber.emplace_back(n);
    }
    sort(gNumber.begin(), gNumber.end()); // 오름 차순 정렬
    int gNumberLen = gNumber.size();
    int start, end = 0;
    int ans = 0x7fffffff;
    for(int i = 0; i < gNumberLen; ++i) {
        start = i;
        while(end < gNumberLen) {
            if(gNumber[end] - gNumber[start] >= M) {
                ans = min(ans, gNumber[end] - gNumber[start]);
                break;
            }
            ++end;
        }
        if(end == gNumberLen) break;
    }
    cout << ans;
    return 0;
}