[알고리즘/문제풀이/BOJ 10816번] 숫자 카드2

숫자 카드 2는 이진탐색을 사용하는 문제입니다. 숫자를 정렬시킨 후 이진 탐색을 하는 문제입니다.

2021.07.19 - [알고리즘/문제풀이] - [BOJ 1920번]수 찾기

[BOJ 1920번]수 찾기

이전 문제와 비슷한 방법을 사용하나 테스트 케이스의 크기가 다르기 때문에 조금은 신경을 써야 했습니다. 정렬의 경우 퀵솔트의 경우 최악의 경우 N^2이 될 수 있어서 시간초과를 내었습니다. 따라서 항상 고르게 시간을 소요하는 병합 정렬을 이용해만 합니다. 이진 탐색의 경우 under bound, upper bound를 찾도록 알고리즘을 약간 변형해야 합니다. 다른 분의 코드를 참고했을 때 딕셔너리, 맵, 해쉬 등의 자료구조를 활용하여 memoization을 수행하여 수행 시간을 더욱 단축시킨 것을 확인할 수 있었습니다.

작성한 코드는 다음과 같습니다.

---

#include<stdio.h>

int N;
int number[500020];
int temp[500020];
int M;
int target;
int temp1;
int cnt;
int low, high, mid;

void mergesort(int low, int high) {

	if (low == high) return;

	int mid = (low + high) / 2;

	mergesort(low, mid);
	mergesort(mid + 1, high);
	int i = low;
	int j = mid+1;
	int index = 0;

	while (1) {
		if (number[i] > number[j]) {
			temp[index] = number[j];
			index++;
			j++;
		}
		else {
			temp[index] = number[i];
			index++;
			i++;
		}

		if (i == mid + 1) {
			while (j <= high) {
				temp[index] = number[j];
				j++;
				index++;
			}
			break;
		}
		if (j == high + 1) {
			while (i <= mid) {
				temp[index] = number[i];
				i++;
				index++;
			}
			break;
		}
	}

	for (int i = 0; i < index; i++) {
		number[i+low] = temp[i];
	}
}

int main(void) {
	int index = 0;

	scanf("%d", &N);

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

	mergesort(0, N - 1);

	number[N] = 123456789;


	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf("%d", &target);

		low = 0;
		high = N;
		while (low < high) {
			mid = (low + high) / 2;
			if (number[mid] < target) {
				low = mid + 1;
			}
			else if (number[mid] >= target) {
				high = mid;
			}
		}

		temp1 = low;

		high = N;

		while (low < high) {
			mid = (low + high) / 2;
			if (number[mid] < target+1) {
				low = mid + 1;
			}
			else if (number[mid] >= target+1) {
				high = mid;
			}
		}

		printf("%d ", low-temp1);
		
	}
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

https://www.acmicpc.net/problem/10816