#10815 숫자 카드

# 문제

# 입력 및 출력

# 풀이

처음에 문제를 보니 메모리가 널널해서 그냥 배열을 써도 되겠다고 생각했다

대신 배열크기를 10,000,000으로 잡고 양수 배열과 음수 배열 2개를 만들어야겠다고 생각함

대신 0이 있기 때문에 양수 배열은 10,000,001 크기로 설정

 

입력받은 수를 인덱스로 사용해서 배열에 1을 저장한다

이렇게 되면 전역변수로 배열을 선언했기 때문에 없는 카드는 자동으로 0이 된다

 

입력받은 값이 양수인지 음수인지만 확인해서 양수면 양수배열에 접근해서 확인하고

음수면 입력받은 값을 양수로 변환 후 음수 배열에 접근해서 확인하면 된다

#include <iostream>
#pragma warning (disable:4996)
using namespace std;

int p[10000001];
int n[10000000];

int main() {
	int N, M, t;
	cin >> N;
	for (int i = 0; i < N; i++) {
		scanf("%d", &t);
		if (t >= 0) p[t] = 1;
		else n[(-1)*t] = 1;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		scanf("%d", &t);
		if (t >= 0) printf("%d ", p[t]);
		else printf("%d ", n[(-1)*t]);
	}
}

 

밑에 알고리즘 분류를 보니까 이분탐색을 쓰는 문제 같아서 이분탐색으로도 풀어봤다

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning (disable:4996)
using namespace std;
vector<int> arr;
int main() {
	int N, M, t;
	cin >> N;
	while (N--) {
		scanf("%d", &t);
		arr.push_back(t);
	}
	sort(arr.begin(), arr.end());
	cin >> M;
	while (M--) {
		scanf("%d", &t);
		int start = 0;
		int end = arr.size() - 1;
		int mid = (start + end) / 2;
		while (1) {
			if (arr.at(mid) < t) {
				start = mid;
				mid += (end - mid + 1) / 2;
			}
			else {
				end = mid;
				mid -= (mid - start + 1) / 2;
			}
			if (arr.at(mid) == t) {
				printf("1 ");
				break;
			}
			if (mid == end || mid == start) {
				printf("0 ");
				break;
			}
		}
	}
}

코드는 길어지지만 이분탐색이 확실이 메모리나 시간 측면에서 더 좋은 것 같다