백준(baekjoon) [C] - 2776번: 암기왕

 

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

2776번: 암기왕

---

#include <stdio.h>  // 암기왕
#include <stdlib.h>

int n, m;
int arr[1000001];
int sort[1000001];

void merge(int* arr, int start, int mid, int end)
{
	int i, j, k;
	i = start;
	j = mid + 1;
	k = start;

	while (i <= mid && j <= end)
	{
		if (arr[i] >= arr[j])
			sort[k++] = arr[j++];
		else
			sort[k++] = arr[i++];
	}

	if (i > mid)
	{
		for (int idx = j; idx <= end; idx++)
		{
			sort[k++] = arr[idx];
		}
	}
	else
	{
		for (int idx = i; idx <= mid; idx++)
		{
			sort[k++] = arr[idx];
		}
	}

	for (int idx = start; idx <= end; idx++)
	{
		arr[idx] = sort[idx];
	}
}

void merge_sort(int* arr, int start, int end)
{
	int mid;
	if (start < end)
	{
		mid = (start + end) / 2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
}

int binary_search(int* arr, int num)
{
	int left = 0;
	int right = n;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arr[mid] == num)
			return 1;
		else if (arr[mid] > num)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return 0;
}


int main()
{
	int t;
	scanf("%d", &t);

	for (int i = 0; i < t; i++)
	{
		scanf("%d", &n);
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &arr[j]);
		}

		merge_sort(arr, 0, n);

		scanf("%d", &m);
		int num;
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &num);
			printf("%d\n", binary_search(arr, num));
		}

		for (int j = 0; j < n; j++)
		{
			arr[j] = 0;
		}
	}

	return 0;
}

---

MEMO

-- 정렬 + 이진탐색 구현만 가능하다면 해결가능

-- 동적할당으로 arr, sort를 할당했다가 메모리초과로 실패

-- 전역변수에 1차원 배열을 만들어서 해결 

 

!! 이진탐색, 병합정렬 생각하지 않고도 코드를 짤 수 있을 때까지 익히기 !!