글 읽기 - C언어로 이분 탐색을 구현했는데 시간 초과로 오답처리 됩니다.

alsrl9 3년 전 0

이분 탐색을 처음으로 구현해봤는데 로직에 문제가 없어보이는데도 Output이 틀렸다고 오답 처리됩니다.

다른 분들의 소스를 봤는데 몇 번을 살펴봐도 저랑 다른 게 없어보여요.

로직의 문제도 못 찾겠고 시간이 오래 걸리는 이유도 모르겠습니다.

도와주실 수 있으신가요?

#include <stdio.h>
#include <stdlib.h>

int A[100000];

int compare(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}

void binarySearch(int start, int end, int target) {

	int mid;
	while (1) {
		mid = (start + end) / 2;
		if (A[mid] == target) {
			printf("1\n");
			return;
		}
		else if (start == end) {
			printf("0\n");
			return;
		}
		else if (A[mid] > target) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
}

int main() {
	int N, M, temp;
	scanf_s("%d", &N);
	for (int i = 0; i < N; i++)
		scanf_s("%d", &A[i]);
	qsort(A, N, sizeof(int), compare);
	scanf_s("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf_s("%d", &temp);
		binarySearch(0, N - 1, temp);
	}

	return 0;
}

djm03178 3년 전 1

start + 1 == end인 상황을 생각해 봅시다. 그러면 mid == start가 됩니다. 여기서 만일 A[mid] > target이면 end = mid - 1이 되면서 end가 start보다 1 작아지게 됩니다. 그 후로는 어떻게 해도 루프를 빠져나갈 수단이 없게 됩니다.

alsrl9 3년 전 0

늦은 시각임에도 답변 달아주셔서 정말 감사합니다.

말씀해주신대로 end가 start보다 작아지는 경우를 고려하지 않고 루프문을 작성했었네요.

그래서 while문에 (start <= end) 조건을 추가했습니다.

그래도 Output이 정답과 달라 오답처리 됩니다.

모든 경우를 탐색하기 때문에 시간이 문제가 될지언정 오답처리가 되는 경우는 도저히 못 찾겠습니다.

염치불구하고 다시 도움을 요청드려도 될까요?

#include <stdio.h>
#include <stdlib.h>

int A[100001];

int compare(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}

void binarySearch(int start, int end, int target) {

	int mid;
	while (start <= end) {
		mid = (start + end) / 2;
		if (A[mid] == target) {
			printf("1\n");
			return;
		}
		else if (A[mid] > target) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
	printf("0\n");
	return;
}

int main() {
	int N, M, temp;
	scanf_s("%d", &N);
	for (int i = 0; i < N; i++)
		scanf_s("%d", &A[i]);
	qsort(A, N, sizeof(int), compare);
	scanf_s("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf_s("%d", &temp);
		binarySearch(0, N - 1, temp);
	}

	return 0;
}

djm03178 3년 전 1

compare 함수의 구현이 잘못되었습니다. 입력 범위 때문에 단순히 뺄셈을 하면 오버플로우가 발생할 수 있습니다. 예를 들어 20억에서 -20억을 빼면 40억이 되어야 하지만 이는 int의 범위를 벗어납니다.

그리고 코드는 반드시 제출했던 코드 그대로를 올려주시기 바랍니다. scanf_s 등 그대로 제출했을 리 없는 흔적이 있으면 답변자는 제출 과정에 크게 수정된 곳이 있지는 않을지 불안감을 감출 수 없게 됩니다.

alsrl9 3년 전 0

답변이 늦어서 죄송합니다.

소스 첨부가 적절하지 않았네요.

말씀하신 부분 참고해서 다음부터는 제출한 코드를 그대로 올리겠습니다.

감사합니다. :)

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

문제

문제

출처

ICPC

C언어로 이분 탐색을 구현했는데 시간 초과로 오답처리 됩니다.

alsrl9 3년 전 0

djm03178 3년 전 1

alsrl9 3년 전 0

djm03178 3년 전 1

alsrl9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말