[1920] 수 찾기(C++)

문제

1920번: 수 찾기

 

 

해결 방법

1. n개의 정수를 배열 a에 입력받는다.

2. 배열 a를 오름차순으로 정렬한다.

3. 배열 a에 존재하는지 알고싶은 숫자들을 하나씩 입력받으면서 직접 구현한 binsearch 함수를 실행한다.

(binsearch 함수는 그냥 일반적인 binary search 함수로 구현하면 된다.)

 

이 문제에서 핵심은 '시간 초과'가 나지 않도록 하는 것이었다.

처음에는 cin, cout, sort()를 사용하여 코드를 짰는데 시간초과가 나서 sort 함수가 문제인가 싶었는데

<algorithm> 헤더에 내장된 함수인 sort 함수는 퀵소트로 구현되어 있기 때문에 시간 복잡도는 nlogn밖에 되지 않는다.

 

따라서 sort 함수가 아닌 다른 곳에서 시간초과가 발생하는 것이었는데,

cin, cout 만 scanf, printf 로 바꿔주니 맞았다고 떴다.

 

두 가지 입출력 방법의 속도 차이는 

cin.tie(NULL) / ios_base::sync_with_stdio(false) 사용시 주의사항

 여기서 확인하도록 하자!

 

 

내 코드(C++)

// [1920] 수 찾기
// https://www.acmicpc.net/problem/1920
// 이분 탐색(Binary Search)
// cin, cout 사용할 경우 시간 초과

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

int binsearch(int key, int left, int right);
vector <int> a;

int main(void)
{
    int n, m, tmp;
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i++) {
        scanf("%d", &tmp);
        a.push_back(tmp);
    }

    // 오름차순 정렬(Quick Sort -> 시간 복잡도 : nlogn)
    sort(a.begin(), a.end());

    scanf("%d", &m);
    for(int i = 0 ; i < m ; i++) {
        scanf("%d", &tmp);
        printf("%d\n", binsearch(tmp, 0, n));
    }
}

// Binary Search
int binsearch(int key, int left, int right)
{
    int mid;
    while(left <= right) {
        mid = (left + right) / 2;
        
        if(key < a[mid]) {
            right = mid - 1;
        }
        else if(key > a[mid]) {
            left = mid + 1;
        }
        else {
            return 1;
        }
    }
    return 0;
}