글 읽기 - c언어 시간초과 질문입니다..(46%)

zkfzpf56 3년 전 0

동일한 값을 탐색할 때 한 점을 기준으로 왼쪽과 오른쪽으로 뻗어나가는 방향으로 구성했습니다.

도와주시면 감사하겠습니다.

#include <stdio.h>
#include <stdlib.h>
int a[500000];
int compare(const void* a, const void* b) {
	if (*(int*)a > * (int*)b)
		return 1;
	else if (*(int*)a < *(int*)b)
		return -1;
	else return 0;
}
int bina(int b, int n) {
	int start = 0;
	int end = n;
	int mid = (end + start) / 2;
	int p = 0;
	int count = 0;
	while (end - start >= 0) {
		if (b == a[mid]) {
			p = 1; break;
		}
		else if (b < a[mid])
			end = mid - 1;
		else
			start = mid + 1;
		mid = (end + start) / 2;
	}
	if (p == 1) {
		int k = mid;
		while (b == a[k]) {
			count++;
			k++;
		}
		k = mid - 1;
		while (b == a[k]) {
			count++;
			k--;
		}
		return count;
	}
	return 0;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int m;
	qsort(a, n, sizeof(int), compare);
	scanf("%d", &m);
	int p;
	for (int i = 0; i < m; i++) {
		scanf("%d", &p);
		printf("%d ", bina(p, n));
	}
}

djm03178 3년 전 0

하나씩 뻗어나가면 최악의 경우 똑같은 값이 10만 개 있고 그 값을 10만 개 찾게 되면 전체를 탐색하는 것과 다를 게 없어집니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어 시간초과 질문입니다..(46%)

zkfzpf56 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말