[BOJ #10816] 숫자 카드 2

BOJ #10816, 숫자 카드 문제입니다.

 

기본적으로 이진 탐색을 이용하는 문제이고 다른 기초적인 이진 탐색 문제와 다르게 이진 탐색을 여러 번 해야 하는 문제입니다. 그래서인지 시간 초과로 틀리는 케이스가 많으며 정답률도 낮은 편입니다.

 

1. 숫자가 있는지 판단하기

기본적인 이진 탐색 알고리즘을 이용하면 되므로 쉽게 짤 수 있습니다.

int M; scanf("%d", &M);
int *toFind = (int *)malloc(sizeof(int) * M);
for (int i = 0; i < M; i++) {
	scanf("%d", &toFind[i]);
	idx = findIdx(card, N, toFind[i]);
	if (idx == -1)
		printf("0 ");
	else
		printf("%d ", numCnt[findIdx(numKind, kind, card[idx])]);
}

findIdx 함수 내에서 이진 탐색 알고리즘을 이용했습니다.

int findIdx(int *arr, int N, int toFind) {
	int left = 0;
	int right = N - 1;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;

		if (arr[mid] > toFind)
			right = mid - 1;
		else if (arr[mid] < toFind)
			left = mid + 1;
		else
			return mid;
	}

	return -1;
}

 

findIdx 함수의 반환값이 -1인 경우엔(if (idx == -1)) 조건을 만족하는 값을 찾지 못한 경우이므로 0을 출력합니다. 그 외(else)에는 numCnt[findIdx(numKind, kind, card[idx])])를 출력하도록 되어 있는데 numKind와 numCnt는 모두 배열입니다. 이 배열에 대해서도 이진 탐색을 이용해서 결과값을 내야 문제를 시간 내에 풀 수 있습니다. 이 두 배열이 무엇인지 다음부터 설명드리겠습니다.

 

2. 숫자의 종류와 해당 숫자의 개수를 담은 배열 컨트롤

numKind 배열은 주어진 숫자 카드들에 있는 숫자들을 중복 없이 담은 배열입니다. numCnt 배열은 해당 숫자 카드의 개수를 담은 배열입니다. 이 두 배열의 길이는 같으며 인덱스는 대응되게 움직입니다.

int kind = getNumKind(card, N);
int *numKind = (int *)malloc(sizeof(int) * kind);
int *numCnt = (int *)malloc(sizeof(int) * kind);

int idx = 0, cnt = 1, prev = card[0];
for (int i = 1; i < N; i++) {
	if (prev == card[i])
		cnt++;

	if (prev != card[i] || i == N - 1) {
		numKind[idx] = prev;
		numCnt[idx++] = cnt;
		prev = card[i];
		cnt = 1;
	}
}

kind 변수의 값을 설정하는 데에 사용된 getNumKind 함수입니다.

int getNumKind(int *card, int N) {
	int cnt = 1;
	int prev = card[0];
	for (int i = 1; i < N; i++) {
		if (prev != card[i]) {
			cnt++;
			prev = card[i];
		}
	}

	return cnt;
}