BOJ 10815 숫자 카드 / C++

문제 링크 : https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

문제 풀이

카드 숫자의 범위가 최소 -10000000부터 최대 10000000이고 메모리 제한은 256MB이므로

bool형 배열을 2천만개 생성하여도 널널하다. 10000001부터는 음수를 체크한다.

 

풀이 방법은 내가 갖고 있는 카드를 입력받음과 동시에 배열에 true로 바꿔주고

숫자 카드를 입력 받음과 동시에 내가 갖고 있는지 판단하여 1 또는 0을 출력한다.

 

참고로, 정렬 후 binary search를 하는 풀이도 생각할 수 있다.

소스 코드

#include <iostream>
using namespace std;

bool cards[20000010] = { 0, };

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

	int n, m;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		
		if (tmp < 0) {
			cards[tmp*(-1) + 10000000] = true;
		}
		else { cards[tmp] = true; }
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		
		if (tmp < 0) {
			if (cards[tmp * (-1) + 10000000] == true) {
				cout << 1 << ' ';
			}
			else {
				cout << 0 << ' ';
			}
		}
		else {
			if (cards[tmp] == true) {
				cout << 1 << ' ';
			}
			else {
				cout << 0 << ' ';
			}
		}
	}
}