[백준 1920] 수 찾기

 

 

처음에는 그냥 이중 포문 써서 했는데 시간 초과가 되는 바람에 다시 한번 생각을 해봤습니다.

고려해야할 조건은

1. 정수의 범위 - int 대신 double 사용

2. time limit - 이중포문 대신 qsort(), 이진 탐색 사용

 

다음은 C언어로 작성한 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
	double ra = *(double*)a;
	double rb = *(double*)b;
	return ra - rb > 0 ? 1 : -1;
}

int main()
{
	double * a, * b;
	int n, m;
	int i, flag = 0;
	int l, r, mi;
	scanf("%d", &n);
	a = (double*)malloc(sizeof(double) * n);
	for (i = 0;i < n;i++) scanf("%lf", &a[i]);
	scanf("%d", &m);
	b = (double*)malloc(sizeof(double) * m);
	for (i = 0;i < m;i++) scanf("%lf", &b[i]);
	qsort(a, n, sizeof(double), compare);
	for (i = 0;i < m;i++) {
		l = 0;
		r = n - 1;
		while (1)
		{
			if (l <= r) {
				mi = (l + r) / 2;
				if (b[i] == a[mi]) { flag = 1;break; }
				else if (b[i] < a[mi]) { r = mi - 1; }
				else if (b[i] > a[mi]) { l = mi + 1; }
			}
			else break;
		}
		if (flag == 1) printf("1\n");
		else printf("0\n");
		flag = 0;
	}
    free(a);
    free(b);
}

 

배운 점

1. 문제의 조건을 잘보자.

2. qsort() 잘 사용하자.

3. 이진탐색