[C++] 백준 1920: 수 찾기

문제 이해

- N개의 정수 A[1] ... A[N]이 주어질 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하라.

 

<입력>

- N: 주어지는 정수의 개수 (1 ~ 100,000, 10^5)

- A[1] ... A[N] (-2^31 ~ 2^31)

- M: 주어지는 X의 개수 (1 ~ 100,000, 10^5)

- X: 찾아야하는 정수 (-2^31 ~ 2^31)

 

<조건>

- 시간제한: 1초

- 메모리제한: 128MB

 

<출력>

- M개의 줄에 출력하고, 존재할경우 1, 존재하지 않을경우 0을 출력하시오.

 

 

문제 풀이

먼저 가장 쉬운 완전 탐색을 생각했을때

N이 10^5, M이 10^5이므로 N * M은 10^10이 되어 가볍게 시간초과가 된다.

 

 

그러므로 더 시간 복잡도가 작은 방법을 선택해야 하는데 바로 이분탐색이다.

이분 탐색은 시간 복잡도가 O(logN)이므로

시간 복잡도는 MlogN이 되어 시간 제한에 맞게 탐색할 수 있다.

 

이분 탐색의 구현 방법은

1. while문을 쓰는 방법

2. stl 라이브러리에 있는 lower_bound와 upper_bound를 쓰는 방법

이 있는데

 

둘 다 익혀두면 좋으므로 둘 다 구현해 보았다.

 

 

 

전체 코드

1. while문을 쓰는 방법은 아래 코드와 같이 진행하였다.

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

int n, m;
int num[100005];

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

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

    sort(num, num+n);

    cin>>m;
    while(m--){
        int x;
        cin>>x;

        int start = 0;
        int end = n-1;
        int mid;

        bool flag = false;
        while(start <= end){
            mid = (start + end) / 2;

            if(num[mid] < x){
                start = mid + 1;
            }else if(num[mid] > x){
                end = mid - 1;
            }else{
                flag = true;
                break;
            }
        }

        if(flag) cout<<"1\n";
        else cout<<"0\n";
    }
    return 0;
}

 

 

2. stl 라이브러리를 쓰는 방법은 아래 코드와 같다.

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

int n, m;
int num[100005];

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

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

    sort(num, num+n);

    cin>>m;
    while(m--){
        int x;
        cin>>x;

        int upperIdx = upper_bound(num, num+n, x) - num;
        int lowerIdx = lower_bound(num, num+n, x) - num;
        if(upperIdx - lowerIdx > 0){
            cout<<"1\n";
        }else cout<<"0\n";
    }
    return 0;
}

 

lower_bound, upper_bound의 사용법을 모른다면 아래 포스트를 참고하도록 하자.

https://dmoritle.tistory.com/entry/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89Binary-Search-lowerbound-upperbound

[C++] 이분 탐색(Binary Search) - lower_bound, upper_bound

 

lower_bound는 찾는 정수가 없을 경우 찾는 정수보다 큰 값 중 가장 작은 값을 리턴한다

upper_bound도 찾는 정수가 없을 경우 찾는 정수보다 큰 값 중 가장 작은 값을 리턴한다.

 

이 문제에서 A[1] ... A[N]안에 X가 없을경우 두 함수 모두 같은 값을 리턴해

그 차이가 0이되어 존재하지 않는지 탐색할 수 있다.

 

 

X가 있을경우 upper_bound는 초과하는 정수의 위치를 리턴하고

lower_bound는 x의 위치 중 가장 작은 위치를 리턴하므로 그 차이는 양수가 될 것이다.