[백준/BOJ/C++] 10815번 숫자 카드 - 이분 탐색

10815번: 숫자 카드

1. 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

---

2. 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

---

3. 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

---

4. 풀이

숫자 카드에 적혀있는 수의 범위가 크기 때문에 모든 숫자를 하나씩 검사하기에는 시간이 너무 오래걸린다. 그래서 이분탐색 기법을 활용하여 문제를 풀어야 한다.

1) 먼저 이분탐색을 하기 위해 상근이가 가지고 있는 숫자카드를 정렬한다.

2) M개의 정수를 각각 이분탐색 기법으로 확인한다.

- start는 0, end는 num_N벡터의 가장 마지막 인덱스로 정하고 시작한다.

- flag 변수를 활용하여 그 숫자가 있는지 없는지를 저장한다. 있을경우에는 answer 벡터에 1을 추가하고, 반복문이 끝난뒤에도 flag 변수가 여전히 0이면 없다는 의미이기 때문에  answer 벡터에 0을 추가한다.

---

5. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> num_N;
vector<int> num_M;
vector<int> answer;

int main(){
    int N, M;
    cin>>N;
    for(int i = 0; i < N; i++){
        int x;
        cin>>x;
        num_N.push_back(x);
    }
    //상근이가 갖고있는 숫자카드 정렬
    sort(num_N.begin(), num_N.end());
    
    cin>>M;
    for(int i = 0; i < M; i++){
        int y;
        cin>>y;
        num_M.push_back(y);
    }

    for(int i = 0 ; i < M; i++){
        int x = num_M[i];
        int start = 0;
        int end = num_N.size() - 1;
        int flag = 0; //그 숫자를 가지고 있으면 1, 아니면 0
        while(start <= end){
            int mid = (start+end)/2;
            if(num_N[mid] == x){
                answer.push_back(1); 
                flag = 1;
                break;
            }
            else if(num_N[mid] < x){
                start = mid + 1;
            }
            else if(num_N[mid] > x){
                end = mid - 1;
            }
        }
        if(flag == 0){
            answer.push_back(0);
        }
    }
    for(int i = 0; i < answer.size(); i++){
        cout<<answer[i]<<" ";
    }
}