숫자 카드

알고리즘 구분 : 정렬, 이분 탐색

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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

문제 풀이

처음에 문제를 보자마자 set container를 이용해서 set에 존재하면 1반환, 없으면 0반환으로 구현하면 바로 풀리겠거니 싶어서 구현을 해서 풀어서 정답을 맞았다. 그러나, 시간이 생각보다 오래걸리기에, 문제에서 원하는 접근 방식이 아닌가 싶어서 확인해 보았더니, 문제에서 원하던 풀이는 이분 탐색이였었다. 그렇기에, 정석적인 이분 탐색 함수를 바로 구현해보았다. 오랜만에 구현하려니까, 조건문에서 사소한 걸 빠뜨려서 시간이 걸렸다.

소스 코드

1) Set Container

#include <bits/stdc++.h>

using namespace std;

#define enld "\n"

int n, m;
set<int> card;
vector<int> check;
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        card.insert(input);
    }
    cin >> m;
    for(int i = 0; i < m; i++) {
        int input;
        cin >> input;
        check.push_back(input);
    }

    solve();

    return 0;
}

void solve() {
    for(int i = 0; i < m; i++) {
        if(card.find(check[i]) != card.end()) {
            cout << 1 << " ";
        }
        else { 
            cout << 0 << " ";
        }
    }

}

2) Binary Search

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> card;
vector<int> check;
bool binarySearch(int start, int end, int num);
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        card.push_back(input);
    }
    cin >> m;
    for(int i = 0; i < m; i++) {
        int input;
        cin >> input;
        check.push_back(input);
    }
    
    solve();

    return 0;
}

bool binarySearch(int start, int end, int num) {
    int mid = (start + end) / 2;

    // start보다 end가 커지는 조건
    if(start > end) {
        return false;
    }
    
    // 찾는 번호가 현재 idx의 value보다 작을 때
    if(num < card[mid]) {
        return binarySearch(start, mid - 1, num);
    }
    // 찾는 번호와 동일할 때
    else if(num == card[mid]) {
        return true;
    }
    // 찾는 번호가 현재 idx의 value보다 클 때
    else {
        return binarySearch(mid + 1, end, num);
    }
}

void solve() {
    sort(card.begin(), card.end(), less<int>());

    for(int i = 0; i < m; i++) {
        if(binarySearch(0, n -1, check[i])) {
            cout << 1 << " ";
        }
        else {
            cout << 0 << " ";
        }
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/10815
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
  1) Set container
  
  2) Binary Search