(c++)백준 10815번: 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

[풀이]

상근이가 가진 숫자카드를 배열에 저장하고 정렬해 놓고, 확인할 카드가 입력될 때마다 이분 탐색으로 해당 수가 있는지 확인하였다.

입출력 때문에 시간 초과가 나서 cin.tie(0)과 ios_base::sync_with_stdio(false)를 추가해줬다.

 

#include <iostream>
#include <algorithm>//sort
using namespace std;
#define Max 500001

int N, M;
int SNum[Max];//상근이가 가지고 있는 숫자 카드들

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> SNum[i];
	}
	sort(SNum, SNum + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		int low = 0;
		int high = N - 1;
		int card;
		bool Yes = false;
		cin >> card;
		while (low <= high) {
			int mid = (low + high) / 2;

			//상근이가 해당 숫자카드를 가지고 있으면
			if (SNum[mid] == card) {
				cout << 1 << ' ';
				Yes = true;
				break;
			}
			if (SNum[mid] < card)
				low = mid + 1;
			else
				high = mid - 1;
		}
		//가지고 있지 않으면
		if (!Yes)
			cout << 0 << ' ';
	}
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	solution();
	return 0;
}