[백준] 10815번 - 숫자 카드

www.acmicpc.net

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

문제

💡

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

시간 제한: 2초

메모리 제한: 256MB

입력

💡

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 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을 공백으로 구분해 출력한다.

예제 입력	예제 출력
5 6 3 2 10 -10 8 10 9 -5 2 3 4 5 -10	1 0 0 1 1 0 0 1

풀이

숫자의 범위는 -1천만 ~ 1천만 까지이고, int형이 2^32이므로 int형으로 충분하다.

선형탐색 시 O(N*M) > 2초, 이진탐색 시 O(M*logN ) < 2초 이므로 이진 탐색을 활용해야 할 것이다.

카드 번호를 배열에 저장한 후 이진탐색을 위해 먼저 정렬을 한번 수행한다.

이후 입력 배열의 원소들을 카드번호 배열에서 하나씩 이진탐색으로 찾는다.

입력을 한 줄에 받기 위해 이전에는 stringstream을 활용했는데,

간단하게 작성하기 위해 cin이 공백을 구분자로 사용하는 것을 이용해 수정했다.

코드


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

using namespace std;

int main() {
	int cardSize;
	cin >> cardSize;

	vector<int> cards;
	int card;
	for (int i = 0; i < cardSize; ++i) {
		cin >> card;
		cards.push_back(card);
	}
	sort(cards.begin(), cards.end());

	int seekSize;
	cin >> seekSize;

	vector<int> seeks;
	int seek;
	for (int i = 0; i < seekSize; ++i) {
		cin >> seek;
		seeks.push_back(seek);
	}

	//search
	for (const int s : seeks) {
		if (binary_search(cards.begin(), cards.end(), s)) {
			cout << "1 ";
		}
		else {
			cout << "0 ";
		}
	}

	return 0;
}