[백준] 수 고르기(2230)

수 고르기(2230번)

문제

N(1≤N≤100,000)개의 수로 이루어진 수열 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(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다

풀이

정렬과 투포인터를 이용하여 풀 수 있는 문제이다.

정렬 O(nlogn), 투포인터 탐색 O(n)의 시간복잡도를 가지므로, 총 O(nlogn)의 시간이 걸린다. N의 범위가 10만이므로, 시간내에 해결 가능.

 

투포인터는, 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 문제를 해결해 나가는 알고리즘이다.
(투포인터를 활용한 대표 문제 : 부분 합(1806번))

 

C++ 소스코드

#include <iostream>
#include <algorithm>

using namespace std;
int M, N, ans= 2e9+1;
int arr[100001];

int findAns() {
    int s = 0, e = 1;
    while (s < N) {
        if (arr[e] - arr[s] < M) {
            e++;
            continue;
        }
        if (arr[e] - arr[s] == M) {
            return M;
        }
        ans = min(ans, arr[e] - arr[s]);
        s++;
    }
    return ans;
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    sort(arr, arr + N);
    printf("%d", findAns());
    return 0;
}

부족한 부분

처음에는 단순히 하나하나의 수에 대해 나를 제외한 다른 모든 수의 차이를 구하는 방식을 생각했다.
근데 N의 범위가 10만이니 N^2의 시간복잡도로는 당연히 풀 수가 없다 ㅎㅎ

 

그래서 2번째로 생각한 것은 배열의 원소 각각에 대해 M만큼 (없으면 1씩 증가하면서) 차이가 나는 원소가 존재하는지 판별하고자 했다.
이것은 맵을 이용하면 된다. key값을 해당 원소로 저장하고, value는 존재유무를 표현하는 bool타입으로 사용한다.

M만큼 차이의 key값이 있는지 찾으면 되므로, 간단하게 해결될 거라 믿었다. (아니면 배열의 인덱스자체를 원소로 두고, 배열값을 bool타입으로 존재유무를 저장해 놓아도 된다.)

 

그러나, 정답이 M이상의 값을 가질 수 있기 때문에 M보다 훨씬 큰 값을 가질 경우, 시간복잡도가 매우 커지게 된다. (M의 범위가 20억인데 O(N*M)이므로 최악의 경우 정말 최악이네 ㄷㄷ )

항상 시간 복잡도에 대한 고민을 할 필요가 있음을 느낀다.