1920. 수 찾기

백준 1920번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1920번: 수 찾기

풀이

아이디어

algorithm 헤더의 find 함수는 시간복잡도가 O(n)이다. 처음에는 아무 생각 없이 간단한 문제인줄 알고 find 함수를 써서 탐색했더니 단번에 시간초과가 났다. M번 반복하여 탐색을 해야 하는데 시간은 짧고 N과 M의 크기는 크기 때문에 시간초과가 날 수도 있겠다는 생각을 하고 같은 algorithm 헤더에 있는 binary_search 함수를 사용해서 O(log2(n))으로 탐색 시간을 줄였다.

binary_search 함수를 사용하기 위해서는 배열이 정렬되어 있어야 하므로 sort 함수로 먼저 정렬해주었다.

이렇게 했는데도 시간초과가 나서 원인을 찾아보니 아래 입출력 최적화 코드를 추가해주지 않아서였다.

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

ios::sync_with_stdio(0)은 C 표준 스트림과 C++ 표준 스트림의 동기화를 끊는 부분이다. 동기화가 되어 있으면 printf, scanf와 같은 C 표준 입출력을 혼용해도 순서가 유지되지만, 사용하는 버퍼 수가 늘어나 입출력이 느려진다. 따라서 이 동기화를 끊어줌으로써 입출력 속도를 향상시키는 것이다.

cin.tie(0)은 cin을 cout으로부터 untie하는 라인이다. stream이 tie되어 있으면 다른 stream에서 입출력 요청이 오기 전에 flush하는데, untie하면 수동으로 flush하지 않는 이상 flush하지 않아 속도가 향상된다.

사실 C 표준 입출력보다는 C++ 표준 입출력이 더 사용하기 쉽기 때문에 이런 편법을 사용하면서도 C++ 표준 입출력을 사용하지만 안정성이 매우 낮아지기 때문에 가능하면 속도 제한이 있을 경우에는 C 표준 입출력을 사용하는것이 좋다고 한다.. 🥲

코드

/*
2021-11-5
1920_수 찾기
https://www.acmicpc.net/problem/1920
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, num, target;
    vector<int> arr;
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> num;
        arr.push_back(num);
    }
    sort(arr.begin(), arr.end());
    cin >> M;
    for (int i = 0; i < M; i++){
        cin >> target;
        if (binary_search(arr.begin(), arr.end(), target))
            cout << "1\n";
        else
            cout << "0\n";
    }

    return (0);
}

시간 / 공간 복잡도

• 시간 복잡도: 정렬 O(N log N) + M번의 이진탐색 O(M log N) = O((N + M) log N)
• 공간 복잡도: 입력 배열 저장으로 O(N)