글 읽기 - 1920 수찾기 퀵소트, 이진탐색 이용했는데 틀리네요ㅠ

kakama 6년 전 0

퀵소트랑 바이너리서치 둘 다 함수를 직접 짜서 돌렸는데

채점이 거의 마지막쯤 가서 틀렸다고 나오네요 ㅠㅠ

찾아보니 비교할 때 integer overflow가 나서 틀리다는 것 같은데,

어떻게 해야 해결할 수 있나요?

비교하는 값들을 long long으로 선언해도 똑같이 틀리더군요.

도움 부탁드립니다 ㅠㅠ

#include <stdio.h>

void QuickSort(int arr[], int left, int right)
{
	int i = left, j = right;
	int pivot = arr[(left + right) / 2];
	int temp;

	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;

		if (i <= j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	} while (i <= j);

	if (left < j) QuickSort(arr, left, j);
	if (right > i) QuickSort(arr, i, right);
}


int BinarySearch(int arr[], int find, int low, int high)
{
	if (low > high) return 0;

	int mid = (low + high) / 2;

	if (arr[mid] > find) 
		return BinarySearch(arr, find, low, mid - 1);
	else if (arr[mid] < find) 
		return BinarySearch(arr, find, mid + 1, high);
	else
		return 1;

}


int main()
{
	int N, M;
	int A[100000] = { 0 };
	int num[100000] = { 0 };
	int i;

	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	scanf("%d", &M);
	for (i = 0; i < M; i++)
		scanf("%d", &num[i]);

	QuickSort(A, 0, N - 1);

	for (i = 0; i < M; i++)
		printf("%d\n", BinarySearch(A, num[i], 0, M - 1));


	return 0;
}

ntopia 6년 전 1

BinarySearch 범위 0부터 N-1 로 해야 맞겠죠?

djm03178 6년 전 1

61번째 줄에 M - 1이 아니라 N - 1입니다. 그리고 이 코드에서 overflow 문제는 발생하지 않습니다.

kakama 6년 전 0

헉 ㅠㅠㅠ 정말 감사드립니다...

이렇게 멍청하게 틀렸을줄은 상상도 못했네요.

두 분 다 정말 감사드려요!!

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

문제

문제

출처

ICPC

1920 수찾기 퀵소트, 이진탐색 이용했는데 틀리네요ㅠ

kakama 6년 전 0

ntopia 6년 전 1

djm03178 6년 전 1

kakama 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말