[백준 10815 C++] - 숫자 카드

2022년 11월 09일

0. 시작

백준 온라인 저지 10815번 문제의 C++ 풀이입니다. M이 500,000 이고, 카드 숫자 간 중복이 없으므로 정렬 & 탐색보다 빠른 Indexing을 활용해서 풀이하였습니다.

1. 문제 생각

N과 M이 서로 500,000씩 크며, 카드의 숫자는 -10,000,000 ~ +10,000,000 입니다.
카드를 char, bool 등 1byte형 배열로 선언하게 된다면 20,000,000 bytes ~= 20MB 이기에 편의를 위해 배열을 활용하기로 했습니다.(단, 스택 영역은 불가)
0으로 초기화, 카드가 입력되면 1 설정의 방식으로 진행할 것입니다. 배열 외에도 bit를 활용하는 등 다양한 방법이 있습니다.

2. 풀이

복잡한 알고리즘은 없으므로 바로 진행하겠습니다.

배열 크기는 20,000,000 + 1 입니다.

배열(cards) 선언 및 0으로 초기화
N 입력
N 에 따라서 카드 숫자(input) 입력 받기
1. Indexing을 위해 input에 10,000,000 더하기(new index)
  
  Ex. -10,000,000 -> 0 & 0 -> 10,000,000 …
2. cards배열 new index 위치 1 설정
M 입력
찾는 카드 번호(input) 입력 받기
1. Indexing을 위해 input에 10,000,000 더하기(new index)
2. cards배열 new index 위치 출력

000. 마무리

정답 코드 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>

#define INDEXING 10000000

bool cards[(INDEXING << 1) + 1] = { 0, };

int main()
{
	int N;

	scanf("%d", &N);

	int input;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &input);
		cards[input + INDEXING] = 1;
	}

	int M;

	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d", &input);
		printf("%d ", cards[input + INDEXING]);
	}
}