[Baekjoon/백준] 10815번: 숫자 카드(C/C++)

단계별로 풀어보기 12단계(집합과 맵) 1번 문제

https://www.acmicpc.net/step/49

집합과 맵 단계

---

백준 10815번: 숫자 카드

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

10815번: 숫자 카드

---

문제 설명

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

---

입력과 출력

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

---

접근 방법

이번 문제는 숫자 카드 개수 N을 입력받아 N개의 숫자 카드 숫자들을 입력해주고, 이후 찾을 숫자 M을 입력받아 M개의 찾을 숫자들을 입력해 각 숫자에 대해 있으면 1을, 없으면 0을 출력하는 문제다.

이 문제는 이전에 풀었던 이분 탐색 문제 숫자 카드 2 에서 숫자 개수 대신 1과 0을 출력하는 것으로, 이 문제 역시 이분 탐색으로 해결할 수 있다.

그냥 간단하게 벡터를 이용해서 N개의 카드 숫자들을 입력하고, 정렬을 한 뒤 정렬된 벡터에 중간 값부터 탐색해서 찾는 숫자보다 현재 벡터의 숫자가 작다면 한칸 앞으로, 크다면 한칸 뒤로 이동해서 찾아서 같은 숫자가 나오면 1을 출력하도록 하면 된다.

---

코드

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

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int N, M, num, start, end, mid, result;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++)
		cin >> v[i];

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

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> num;

		start = 0;
		end = N - 1;
		result = 0;

		while (end >= start) {
			mid = (start + end) / 2;
			if (v[mid] == num) {
				result = 1;
				break;
			}
			else if (v[mid] < num)
				start = mid + 1;
			else
				end = mid - 1;
		}

		cout << result << " ";
	}

	cout << "\n";

	return 0;
}

---

결과

백준 제출 결과

시간제한이 2초라서 그냥 간단하게 생각하고 ios_base::sync_with_stdio(0); cin.tie(0); 전부 다 쓰지 않았는데 결국 다 틀려버렸다..