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

백준 온라인 저지(BOJ) 10815번 숫자 카드
https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

* 사용언어 : C언어, C++
 

1. 문제

숫자 카드 N개를 가지고 있는 상황에서
M개의 정수가 주어졌을 때 각 카드가 있는지를 1 또는 0 으로 출력

 

2. 풀이

이 문제는 2가지 방법으로 풀어보았습니다. (배열 인덱스 활용, Hash 응용)
 
아래 작성한 두 방법 모두 정답이 되니 참고해보시고
더 좋은 아이디어가 있다면 댓글로 공유 부탁드립니다.
 

1) 배열 인덱스 활용

문제의 메모리 제한이 넉넉해서 int 배열을 선언해서 풀 수 있었습니다.
배열의 인덱스를 카드의 숫자로 보고 그 자리에 1을 적어두는 방식입니다.
(4 byte * 20,000,001 는 약 76MB)
 
단, 입력이 -10,000,000 부터 들어오기 때문에
입력 숫자에 10,000,000 을 더한 후 0 부터 20,000,001 로 변경했습니다.
이후 내용은 단순하니 아래 코드로 설명을 대체하겠습니다.
 
해당 풀이는 코드가 간결하고 이해하기 쉽다는 장점이 있지만
메모리를 불필요하게 많이 사용한다는 단점이 있습니다.
 

2) Hash 응용

1번 풀이의 단점을 보완하기 위해 Hash Table 을 응용해보았습니다.
카드는 최대 50만 개인데 배열을 2,000만 개나 선언해둘 필요가 없다는 생각에서 시작된 풀이입니다.
 
입력으로 주어진 카드의 숫자는 Hash 처리하여 작은 숫자로 만들었고
이 값에 해당되는 index 에 입력받은 숫자를 기록하는 방식입니다.
 
Hash 의 충돌 방지는 Open Addressing 방식으로 해결했고
공간이 부족하지 않도록 50만이 아닌 50만 * 5 로 넉넉하게 구성했습니다.
(메모리 사용 : 79,236KB → 10,880,KB)
 
Hash Table 의 크기는 5보다는 2 나 3을 곱한 값이 더욱 적합할 것 같지만
Hash 를 구현하고 응용해본 것에 의의를 두고 굳이 더 Test 해보지 않았습니다.
 
 
한 가지 강조하고 싶은 점은 Table 에 넣는 값을 0 base 가 아닌 1 base 로 처리했다는 점 입니다.
 
문제에서 주어지는 음수를 처리하기 위해 어차피 BASE 값을 더해주어야 하는데
이 때는 1번 풀이와 다르게 10,000,000 이 아닌 10,000,001 을 더해서 최소값이 1이 되게 했습니다.
 
이렇게 하면 Hash Table 을 굳이 다른 값(ex. -1)으로 초기화할 필요가 없습니다.
(전역 변수로 선언된 int 의 초기값이 0 이기 때문)
 
0 base 가 아닌 1 base 구현은 SW 개발자로서 받아들이기 어려울 수도 있는 부분이지만
간결한 코드 작성에 도움이 될 때가 많으니 활용해보시기를 권장합니다.
(1 base 를 활용 시 heap 에서 부모 ↔ 자식 간 index 처리도 상당히 간결해집니다)
 
cf) 1 base 를 활용한 heap 구현 풀이 예시
https://rightbellboy.tistory.com/248

[백준/BOJ] 1181번 단어 정렬 (C/C++)

 

3. 코드

1) 배열 인덱스 활용

79,236KB 340ms

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10815_숫자 카드
79236KB	340ms
*/
#include <cstdio>

const int BASE = 10000000;
const int LM = BASE * 2 + 1; // [-10,000,000, 10,000,000]
int a[LM], n, m, v;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		a[v + BASE] = 1;
	}

	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d", &v);
		printf("%d ", a[v + BASE]);
	}
	return 0;
}

 

2) Hash 응용

10,880KB 296ms

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10815_숫자 카드
10880KB	296ms
*/
#include <cstdio>

const int BASE = 10000001;
const int HLM = 500000 * 5;
int ht[HLM], n, m, v;

int hash(int v) {
	return (v + BASE) % HLM;;
}

void add_hash(int v) {
	int h = hash(v);
	int cnt = HLM;
	while (cnt--) {
		if (!ht[h]) {
			ht[h] = v;
			break;
		}
		h = (h + 1) % HLM;
	}
}

int find_hash(int v) {
	int h = hash(v);
	int cnt = HLM;
	while (cnt-- && ht[h]) {
		if (ht[h] == v) {
			return 1;
		}
		h = (h + 1) % HLM;
	}
	return 0;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		add_hash(v);
	}

	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d", &v);
		printf("%d ", find_hash(v));
	}
	return 0;
}