[백준 S4] 숫자 카드 (10815번)

www.acmicpc.net/problem/10815

10815번: 숫자 카드

문제

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

 

입력

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

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

 

출력

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

 

예제 입력 1

5

6 3 2 10 -10

8

10 9 -5 2 3 4 5 -10

 

예제 출력 1 

1 0 0 1 1 0 0 1

 

소스코드 및 풀이

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

using namespace std;

bool binary_search(const vector<int>& cards, int beg, int end, int input)
{
    if(beg > end)
        return false;

    if(beg == end) {
        if(cards[beg] == input)
            return true;
        return false;    
    }

    int mid = (beg + end)/2;
    if(cards[mid] == input)
        return true;   
    if(input < cards[mid])
        return binary_search(cards, beg, mid-1, input);
    return binary_search(cards, mid+1, end, input);    
} 

int main(void)
{ 
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);  
    
    int N;
    cin >> N;

    vector<int> cards(N);
    for(int i=0; i<N; ++i)
        cin >> cards[i];

    sort(cards.begin(), cards.end());
    
    int M;
    cin >> M;

    int input;
    for(int i=0; i<M; ++i) {
        cin >> input;
        if(binary_search(cards, 0, cards.size()-1, input))
            cout << 1 << ' ';
        else
            cout << 0 << ' ';    
           
    }    
    cout << endl;
    return 0;
}

* 50만개의 데이터 입력을 보고 느낌이 오긴했지만, 역시나 <algorithm.h>의 find() 같은 함수를 활용하거나 linear search를 활용하려 들면 시간초과가 뜬다.

* 이분탐색을 통해서 문제를 풀었는데, 이분탐색은 정렬이 되어있는 데이터를 가정하므로 sort()를 통해 미리 정렬을 해줬다.

* 이분탐색을 직접 구현했지만 사실, map과 같은 자료형을 사용해도 되지않을까 하는 생각이 들었다.