글 읽기 - 어디가 틀렸을까요ㅠㅠㅠ 도와주세요ㅠㅠ

whazzulookinat 5년 전 0

구현언어는 C이고, 이분탐색으로 구현하였습니다.

결과가 틀렸다고 나오는데, 어느 부분에서 정답과 다른 결과를 내는지 모르겠습니다. 혹시 모든 int에 대해 받아야하는데 array의 크기가 그것보다 작은 것이 원인이라면, 그 경우에도 틀렸습니다 라고 결과가 뜨나요..? 배열 크기보다 커질 경우 런타임 에러를 예상했는데 틀렸다는 결과를 받아서, 혹시 다른 부분에서 잘못한게 있나 궁금합니다ㅠㅠ

#include<stdio.h>
#include<stdlib.h>
int comp(const void*arg1, const void*arg2) {
	int*a = (int*)arg1;
	int*b = (int*)arg2;
	if (*a > *b) {
		return 1;
	}
	else if (*a < *b) {
		return -1;
	}
	else {
		return 0;
	}
}
int left; int right; int input[1000000]; void scan(int left, int right, int target);
int main(void) {
	int num; int ninput = 1;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		for (int i = 0; i < ninput; i++) {
			input[i] = 0;
		}
		scanf("%d", &ninput);
		for (int i = 0; i < ninput; i++) {
			scanf("%d", &input[i]);
		}
		qsort(input, ninput, sizeof(int), comp);
		int nsearch; int target;
		scanf("%d", &nsearch);
		for (int i = 0; i < nsearch; i++) {
			scanf("%d", &target);
			scan(0, ninput - 1, target);
		}
	}
	return 0;
}
void scan(int left, int right, int target) {
	if (left > right) {
		printf("0\n");
		return;
	}
	int mid = (left + right) / 2;
	if (target == input[mid]) {
		printf("1\n");
		return;
	}
	else if (target > input[mid]) {
		left = mid + 1;
		scan(left, right, target);
	}
	else if (target < input[mid]) {
		right = mid - 1;
		scan(left, right, target);
	}
}

djm03178 5년 전 0

이 문제를 O(NlogN)에 풀고자 한다면 상당히 최적화를 해야 합니다. 사실 무엇보다도 입력을 빠르게 받는 것만큼 이 문제를 푸는 데에 도움이 되는 것이 없지만, 해싱을 통해 좀 더 빠르게 할 수도 있습니다.

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

문제

문제

출처

ICPC

어디가 틀렸을까요ㅠㅠㅠ 도와주세요ㅠㅠ

whazzulookinat 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말