[투 포인터] 수 고르기 - 백준 2230번

2230번: 수 고르기

무수히 많은 도전..

런타임 에러(OutOfBounds)

vector<int> b(N);
while(i<(N-1)) {
        // cout << a[i] << " " << a[j] << "\n";
        if(a[i] <= a[j]) {
            if(a[j] - a[i] >= M) {
                b[count++] = (a[j] - a[i]);
            }
        } else {
            if(a[i] - a[j] >= M) {
                b[count++] = (a[i] - a[j]);
            }
        }
        j++;
        if(j >= N) {
            i++;
            j = i+1;
            if(j>=N) break;
        }
    }

• count가 N 보다 커질시 배열의 영역을 벗어난다.

  j≥N 이 범위에 안들시 무한루프가 된다. count는 계속해서 커진다…

메모리 초과

vector<int> a(N);
vector<int> b(N);

• 메모리 제한 : 128 MB

  두개의 벡터까지는 안되나 보다.

  vector b를 사용하지 않고 mindiff = min(mindiff, diff); 으로 사용

시간초과

• Sort의 중요성!

  결국엔 최소 차이값을 구하는 문제 → 최대 차이값까지 구할 필요가 없다.

  Sort를 통해 뒤에서 운좋게 맞으면 끝까지 배열을 돌려볼 필요가 없다(O(n^2))

  Two Pointer(O(N)) + Sorting (O(NlogN)) = O(NlogN)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() 
{
    int N,M;

    cin >> N >> M;

    vector<int> a(N);

    for(int i=0;i<N;i++) {
        cin >> a[i];
    }

    int i=0;
    int j=1;
    int mindiff = 2000000000;
    sort(a.begin(), a.end());

    while (i < N && j < N) {
        int diff = a[j] - a[i]; // 현재 포인터가 가리키는 두 원소의 차이 계산

        // 두 원소의 차이가 M 이상인 경우
        if (diff >= M) {
            mindiff = min(mindiff, diff); // 최소 차이 갱신
            i++; // 차이를 줄이기 위해 시작 포인터를 오른쪽으로 이동
        } else {
            // 차이가 M 미만인 경우, 차이를 늘리기 위해 끝 포인터를 오른쪽으로 이동
            j++;
        }

        // 두 포인터가 같아지면, 끝 포인터를 오른쪽으로 이동하여 다시 차이를 계산할 수 있게 함
        if (i == j) {
            j++;
        }
    }
   
    cout << mindiff;

}