백준 1920 수 찾기 C++

- 문제

문제 보러가기

- 문제 풀이

• 입력으로 들어 온 배열에 수가 있는지 없는지 찾는 간단한 문제이다. 먼저 생각해볼 수 있는건 선형 탐색으로 수가 입력 배열의 크기만큼 루프를 돌면서 해결할 수 있다. 해당 기능을 구현하면 O(n^2)의 로직이 되고 최악의 경우 10만 x 10만의 루프를 돌아야한다. 따라서 다른 우리는 다른 탐색 기법을 고려해야한다.
• 이진 탐색법은 탐색의 대상인 데이터가 미리 오름차순이나 내림차순으로 정렬되어 있는 경우에 사용할 수 있는 탐색 알고리즘이다. 위 문제에서 n 길이의 입력 배열을 O(nlog n)의 시간복잡도를 갖는 정렬 후 이분탐색을 하면 O(nlog n) * O(m) * O(nlog n) 의 시간복잡도로 구현할 수 있다.
• 해당 문제는 배열을 정렬하고 이진탐색을 통해 해결 할 수 있다. 하지만 자료구조 set을 활용하여 조금 더 시간을 절약할 수 있다. set은 중복값을 허용하지 않는 Key라 불리는 원소들의 집합이며 insert시 정렬이 이루어진다. set의 insert 시 시간복잡도는 O(log n), find의 시간복잡도는 O(log n)인데, 결국 이분탐색을 통한 시간복잡도와 같은 결과를 갖는다 하지만 문제에서 배열의 값이 중복될 수 있다는 점을 주목하면 시간복잡도를 O(log (n-중복된 수))라는 이점을 취할 수 있다.

- 코드

#include <iostream>
#include <set>

using namespace std;

set<int> mySet;

void TieCin() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

int main() {
    TieCin();
    int n, m, input;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
        mySet.insert(input);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> input;
        if (mySet.find(input) != mySet.end())
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    }
    return 0;
}