1 분 소요

1. 문제

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

수 찾기는 n개의 수가 주어진다. 각 수는 2^-31~2^31, 즉 int 범위의 정수이다.

이후 m개의 수가 주어지는데, 이 수들이 좀 전에 주어진 n개의 수 중에 있는지 확인하는 문제이다.

2. 해결

이진 탐색으로 존재하는 지 찾으면 간단하게 끝난다.
C++은 algorithm을 include하면 binary_search 함수를 지원하기 때문에 간단하게 끝난다.
물론 이진 탐색을 하기 전에 수를 오름차순 정렬해야 한다.
이 또한 algorithm 헤더에 sort가 있어 간단하게 할 수 있다.

3. 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    cin >> n;
    int key;
    for (int i = 0; i < n; i++) {
        cin >> key;
        cout << binary_search(A.begin(), A.end(), key) << "\n";
    }
    return 0;
}

4. 마무리

정말 간단한 문제인데 정말 오래걸렸다.
상술한 방법으로도 풀어보고, 직접 이진 탐색과 퀵 정렬까지 구현해 풀어보기도 했지만 항상 시간 초과가 났다.
시간 초과를 해결한 방법은 알고리즘을 다시 짜는 것이 아니어서 좀 많이 허무했다.
바로 입출력 스트림에서의 시간을 줄이는 방법이었다.
ios_base::sync_with_stdio(false)와
cin.tie(nullptr)이 그것이다.
위의 것은 C의 라이브러리인 stdio와의 동기화를 해제하는 것이다. C의 라이브러리를 사용하는 코드가 있다면 순서가 꼬여 사용할 수 없지만 C++ 라이브러리만 사용한다면 훨씬 빠른 입출력이 가능하다.
아래 것은 입력과 출력 스트림의 묶음을 풀어 입출력이 여러 번 반복될 시 속도를 향상시킨다.

사실상 이 문제를 풀고 얻은 것은 이진 탐색으로 빠른 탐색을 구현하는 것이 아니라 입출력 시 위의 것들을 상황에 따라 추가하면서 입출력 속도를 빠르게 할 수 있다는 것을 안 점이다.
앞으로는 알고리즘 뿐 아니라 사소한 부분에서도 속도를 빠르게 해 효율을 높이는 방법을 잘 생각해 보아야 겠다.

카테고리:

업데이트: