백준 10815번: 숫자 카드

[문제 링크]

10815번: 숫자 카드

---

간단한 이분탐색 문제였다. 입력받은 숫자들을 오름차순으로 정렬하고, 그 다음으로 입력받는 정수들을 이분 탐색을 통해 검색해 존재할 경우 1, 존재하지 않을 경우 0을 출력해주면 원하는 결과를 얻을 수 있다.

ps. 입력과 출력의 횟수가 크기때문에 ios_base::sync_with_stdio(0); 과 cin.tie(NULL); 을 추가해주는 것이 좋다.

(대부분의 시간초과는 입출력 부분에서 잡아먹는 시간때문에 발생한다.)

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		bool state = false;
		int start = 0, end = card.size()-1;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			if (num < card[mid])
				end = mid-1;
			else if (num > card[mid])
				start = mid+1;
			else
			{
				cout << "1 ";
				state = true;
				break;
			}
		}
		if (!state) cout << "0 ";
	}

	return 0;
}

 

또한 c++의 set 컨테이너에 정수를 담고 set의 멤버함수인 find() 를 사용하면 매우 간단하게 구현할 수 있다.

#include <iostream>
#include <set>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	set<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.insert(num);
	}
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		if (card.find(num) != card.end()) cout << "1 ";
		else cout << "0 ";
	}
	return 0;
}

알고리즘 200일 프로젝트 - 44day