[백준] 10815 숫자 카드 (C++)

 

 

입출력

 

 

 

 

---

풀이 

 

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

using namespace std;

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


    ///상근이 카드
    int n;
    cin >> n;

    int card_S;
    vector<int> nums_S;
    for (int i = 0; i < n; i++)
    {
        cin >> card_S;
        nums_S.push_back(card_S);
    }

    sort(nums_S.begin(), nums_S.end());


    /// 주어진 카드
    int m;
    cin >> m;

    int card;
    vector<int> cards;
    for (int i = 0; i < m; i++)
    {
        cin >> card;
        cards.push_back(card);
    }

    /// 탐색
    int indexL, indexM, indexH;
    bool exist = false;

    for (int j = 0; j < m; j++) //  주어진 카드 cards
    {
        indexL = 0;
        indexH = n - 1;
        indexM = (indexL + indexH) / 2;

        while (indexH > indexL)
        {
            if (cards[j] > nums_S[indexM])
            {
                indexL = indexM + 1;
                indexM = (indexL + indexH) / 2;
            }
            else if (cards[j] < nums_S[indexM])
            {
                indexH = indexM - 1;
                indexM = (indexL + indexH) / 2;
            }
            if (cards[j] == nums_S[indexM])
            {
                cout << "1 ";
                exist = true;
                break;
            }
            exist = false;
        }

    	if (!exist)
            cout << "0 ";
    }
    

}

 

상근이의 카드와 주어진 카드를 각각 입력받아 벡터에 저장한다

빠른 탐색을 위해 이분 탐색을 이용한다