BOJ 1920 - 수 찾기 문제풀이

문제를 읽고 이해하기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

재정의와 추상화

문제를 보고 처음 딱 떠오른 algorithm 헤더의 STL 함수가 2개가 있다. 하나는 find(), 하나는 binary_search()이다. 그러면 두 함수를 비교분석해보자.

find 함수

• n개의 element에 대해 O(n)의 시간 복잡도를 가진다.
• 하나 하나 찾는 것이므로, 정렬이 필요가 없다.
• 이는 alrogithm 헤더에 있는 find() 함수에 대한 것이므로, set, map 등에서의 find() 함수는 시간 복잡도가 다르다.

binary_search 함수

• 정렬된 n개의 element에 대해 O(logn)의 시간 복잡도를 가진다.
• 정렬되어 있어야 하므로, O(nlogn)의 시간 복잡도를 가지는 sort() 함수를 먼저 사용해야 한다.

언뜻보면, binary_search가 sort 함수를 함께 써야하기 때문에 더 느리다고 생각할 수 있는데, 실제로 계산해보면 그렇지 않다.

M개의 정수 각각을 배열 A에 있는 N개의 정수에 대해서 탐색해야 하므로, find 함수와 binary_search 함수 + sort 함수를 썼을 때의 시간 복잡도는 아래와 같다.

1. find 함수 : M * O(N) = O(MN)
   N과 M을 각각 최댓값인 100,000으로 두면, 약 10억(약 10초)
2. binary_search 함수 : O(NlogN) + M * O(logN) = O((N + M)logN)
   N과 M을 각각 최댓값인 100,000으로 두면, 약 20만(약 0.002초)

코드 작성

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

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    int a[100000], b[100000];

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> b[i];

    sort(a, a + n);
    for (int target = 0; target < m; target++)
        cout << binary_search(a, a + n, b[target]) << '\n';

    return 0;
}

비고

binary_search 함수와 find 함수를 사용했을 때 각각 소요된 시간