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

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

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이상인 두 수를 고를 수 있다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,m, ans = 2e9 + 1;
int v[100001];

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

    cin >> n>>m;

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    sort(v,v+n);

    int left = 0, right = 1;
    while (left < n) {
        if (v[right] - v[left] < m) {
            right++;
            continue;
        }
        if (v[right] - v[left] == m) {
            cout << m;
            return 0;
        }
        ans = min(ans, v[right] - v[left]);
        left++;
    }
  
    cout << ans;
}

문제 풀이

투 포인터 문제이다.

1. 먼저 입력받은 수열을 오름차순으로 정렬한다. (중요한 부분!)

2. left를 가리키는 인덱스가 n보다 작을 때 까지 반복하며,

3. 만약 right가 가리키는 수와 left가 가리키는 수의 차이가 m보다 작을 때는 차이를 늘리기 위해 right를 하나 감소시켜준다.

4. 만약 차이가 딱 m만큼 난다면, 당연히 제일 작은 차이이므로 m을 출력하고 종료한다.

5. 만약 차이가 m보다 크다면, 새로 구한 차이와 기존 ans값을 비교하여 더 작은 것을 ans에 넣는다.

그리고 차이를 줄이기 위해 left를 ++한다.

6. 탐색이 끝나면 ans에는 정답이 들어있으므로 출력해준다.

​

사실 시간초과만 걸리지 않는다면, 어떻게든 풀 수 있는 문제이다.

이전에 비슷한 문제에서 이중 for문을 사용했다가 O(N^2)의 시간복잡도로 인해 N의 범위가 10만이라 시간초과가 났다.

또한,

int left=0,right=1;
while (1) {
        if (abs(arr[left] - arr[right]) >= m) {
            ans = min(ans, abs(arr[left] - arr[right]));
        }
        right++;
        if (right == n) {
            left++;
            right = left;
            if (left == n - 1) break;
        }
    }

위와 같은 코드처럼 정렬해주지 않고, left가 0일 때 right가 끝까지 가고

right가 끝까지 배열의 끝까지 갔다면 left를 1증가시켜서 다시 right를 끝까지 보내면서 탐색하는 것도 마찬가지로 O(N^2)의 시간복잡도를 가지므로 불가능하다.

​

따라서 수열을 정렬해준 뒤, O(n)만큼만 탐색해야한다. 정렬 O(nlogn), 투포인터 탐색 O(n)의 시간복잡도를 가지므로, 총 O(nlogn)의 시간이 걸린다. N의 범위가 10만이므로, 시간내에 해결 가능하다.