[BOJ 10815 // C++] 숫자 카드

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10815번 문제인 숫자 카드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10815

10815번: 숫자 카드

이 문제는 binary search 구현을 연습할 수 있던 문제이다.

가지고 있는 카드를 크기순으로 정렬해두고, 들어오는 숫자마다 binary search를 이용하면 쉽게 풀 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int card[500000]; //카드배열
int target; //배열에 들어있는지 확인할 대상
int mid; //binary search에서 이용
bool chk; // 카드배열에서 target을 찾았는지 확인
int a, b; //binary search에서 이용

int main()
{
    std::ios::sync_with_stdio(0); 
    cin.tie(0); // input이 많다
    int n; //카드의 배열을 받아 정렬
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        card[i] = x;
    }
    sort(card, card + n);
    int y; // 하나씩 숫자를 받아서 binary search로 배열에 있는지 확인
    cin >> y;
    for (int i = 0;i < y;i++) {
        a = 0, b = n - 1;
        cin >> target;
        chk = true;
        while (a <= b) {
            mid = (a + b) / 2;
            if (card[mid] == target) {
                cout << 1 << ' ';
                chk = false;
                break;
            }
            else if (card[mid] < target) {
                a = mid + 1;
            }
            else {
                b = mid - 1;
            }
        }
        if (chk) {
            cout << 0 << ' ';
        }
    }
}