[BOJ / C++] 수 고르기 (투포인터)

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

 

1. 코드

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

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

    int n, m;
    cin >> n >> m;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    int mn = 0x7fffffff;
    int en = 0;
    for (int st = 0; st < n; st++) {
        while (en < n && arr[en] - arr[st] < m) en++;
        if (en == n) break; // en이 범위를 벗어날 시 종료
        mn = min(mn, arr[en]-arr[st]);
    }
    cout << mn;
}

 

 

2. 시간복잡도

n = 100,000이므로 O(n^2)으로 가면 시간초과가 나게 된다. 따라서 O(nlgn)으로 시간복잡도를 낮춰야한다. 일단 정렬을 하는데 O(nlgn)이 걸리고 투포인터로 min을 계산하는데 O(2n)이 걸리게 된다. st, en 모두 index-0에서 시작하지만 매 iteration마다 en이 한칸 이상 이동하거나 아니면 바로 st가 한칸 이동하므로 최대 O(2n)이 걸리게 된다.

 

 

3. 분석

시간복잡도를 낮추는 것이 핵심인데 정렬 후 i + m을 이분탐색으로 lower_bound를 찾는 방법도 있다. 이 방법도 O(nlgn)으로 시간내에 통과 가능하다. 투 포인터를 사용하면 O(2n)에 통과가 가능하다.