백준 1920번: 수 찾기

문제

[BOJ][C++] 백준 1920번: 수 찾기
문제는 링크를 클릭해서 볼 수 있다.

풀이

문제 조건에서 n과 m의 크기는 최대 100,000이다. 시간 제한 1초를 맞추기 위해 시간 복잡도를 고려해야한다. 선형 탐색을 선택할 경우 시간 복잡도는 O(n m)으로 1초의 시간 제한을 넘기게 된다. 따라서 O(log N)의 시간복잡도를 가지는 이분 탐색을 선택했다. 이분 탐색을 선택할 경우 시간 복잡도는 O(n log m)이 되어 시간 제한을 맞출 수 있다.

정수 a들을 a_array에 입력받은 뒤 이분 탐색 알고리즘을 사용하기 위해 a_array를 오름차순으로 정렬했다. left, mid, right는 a_array의 인덱스를 저장한 변수이다. left와 right의 초기값은 각각 0과 n - 1이다.

left가 right보다 작거나 같은 조건에서 반복문을 돌면서 a_array[mid]와 x의 값을 비교했다. x는 a_array안에 존재하는지 알아내려는 정수이다.

a_array[mid]가 x와 같은 경우, 즉 원하는 값을 찾은 경우 1(true)를 출력하고 종료한다. a_array[mid]가 x보다 큰 경우 right을 mid - 1로 바꾸어 보고 있는 범위를 a_array[mid]보다 작은 범위로 바꾼다. a_array[mid]가 x보다 작은 경우 left을 mid + 1로 바꾸어 보고 있는 범위를 a_array[mid]보다 큰 범위로 바꾼다. 이분 탐색이 끝날 때까지 x를 찾지 못했다면 0(false)를 출력하고 종료한다.

공부

시간 복잡도를 계산했을 때는 1초의 시간제한을 넘지않았다. 그런데 첫 제출에서 시간 초과가 나왔다. 혹시 정렬할 때 시간이 오래 걸리지 않을까 고민했지만 sort 함수는 퀵소트 알고리즘을 사용하기에 이 부분도 아니었다. 구글링을 해보니 범인은 cin이었다.

cin, cout은 데이터의 자료형을 명시할 필요가 없어 scanf, printf에 비해 편리하게 사용할 수 있다. 하지만 cin은 scanf에 비해 수행시간이 느리다. ( 10^7개의 숫자를 입력받을 때 std::cin은 2.051초이고, scanf는 수행시간이 0.798초이다. )

cpp의 iostream은 input output stream을 뜻한다. 여기서 stream은 프로그램과 입출력을 하는 단말기(키보드) 사이에 연결된 가상의 입출력 통로를 말한다. c++의 stream은 c의 stream과 동기화 되어 있어 c++ 스타일 코드와 c 스타일 코드가 "같은" stream buffer에 쌓이게 된다. 따라서 c와 c++의 입출력을 혼용할 수 있지만 프로그램의 속도는 scanf, printf보다 느리게 된다.

std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

이 3줄의 코드를 입력하면 cpp의 iostream과 C의 studio의 동기화를 끊고 각각 독립적인 buffer를 가지게 된다. 동기화를 끊으면 사용하는 buffer의 수가 줄어 입출력 속도가 빨라진다.

이때 수행시간은 cin 0.5938초, cout 0.8272초이다. 하지만 buffer 시스템을 끊었기 때문에, studio의 printf, scanf, getchar 등의 함수를 사용할 수 없고 multi-threading시 충돌이 발생할 수 있다. 알고리즘 문제를 풀 때 단순히 single-thread 환경에서 출력만 하기 때문에 이 방법을 사용할 수 있다.

코드

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

int n, m;                       // a_array 배열의 길이, 찾고자하는 정수 x의 개수
int a_array[1000000];           // 정수 a를 저장한 배열
int temp;

void binary_search(int x) {
    int left = 0, mid = 0, right = n - 1;

    while (left <= right) {
        mid = (left + right) / 2;

        // 탈출 조건 : a_array에서 x를 찾은 경우
        if (a_array[mid] == x) {
            cout << 1 << "\n";
            return;
        } else if (a_array[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // 이분 탐색이 끝날 때까지 x를 찾지 못했다면 0(false)를 출력한다.
    cout << 0 << "\n";

    return;
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a_array[i];
    }

    // 이분 탐색 알고리즘을 적용하기 위해 배열을 오름차순으로 정렬한다.
    sort(a_array, a_array + n);
    
    cin >> m;

    int x;
    for (int i = 0; i < m; i++) {
        cin >> x;
        binary_search(x);
    }

    return 0;
}

채점 결과