글 읽기 - 계속 틀렸다고 나오네요...

Conatuseus 7년 전 0

퀵소트하고 이진탐색으로 했습니다

예제 결과는 똑같이 나오고 테스트 몇개 해봤는데 잘 나옵니다...

근데 자꾸 틀렸다고 나와요 ㅠㅠ

도와주십쇼....

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


int compare(const void * a, const void * b);
int binarySearch(int* arr, int left, int right, int find);

int main() {
	int A[100001] = { 0, }; 
	int B[100001] = { 0, };
	int i, j;
	int a, b;
	int left, right, mid;
	scanf("%d", &a);
	for (i = 0; i < a; i++) {
		scanf("%d ", &A[i]);
	}
	scanf("%d", &b);
	for (i = 0; i < b; i++) {
		scanf("%d", &B[i]);
	}
    //A배열 퀵소트.
	qsort(A, a, sizeof(int), compare);
	for (i = 0; i < b; i++) {
        //이진탐색으로 A배열에 B[i]가 있는지 확인해서 1 출력
		if (binarySearch(A, 0, a - 1, B[i]) == 1)
			printf("1\n");
		else
			printf("0\n");

	}



	return 0;
}

int compare(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}
// 이진탐색 (탐색 후 있으면 return 1, 없으면 return 0)
int binarySearch(int* arr, int left, int right, int find) {
	int mid = (left + right) / 2;

	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] == find) {
			return 1;
		}
		else if (arr[mid] < find) {
			left = mid + 1;
		}
		else if (arr[mid] > find) {
			right = mid - 1;
		}
	}
	return 0;

}

deneb2016 7년 전 1

이거 진짜 이상하네요..

여기서 qsort대신 C++ sort 사용하니까 맞는데,

그렇다고 qsort사용법이 잘못된거 같진 않은데, 왜틀리지..

deneb2016 7년 전 2

이렇게 하면 accept뜨네여

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
using namespace std;

int compare(const void * a, const void * b);
int binarySearch(int* arr, int left, int right, int find);

int main() {
    int A[100001];
    int B[100001];
    int i, j;
    int a, b;
    int left, right, mid;
    scanf("%d", &a);
    for (i = 0; i < a; i++) {
        scanf("%d ", &A[i]);
    }
    scanf("%d", &b);
    for (i = 0; i < b; i++) {
        scanf("%d", &B[i]);
    }


    //A배열 퀵소트.
    //qsort(A, a, sizeof(int), compare);
    sort(A, A + a);
    for (i = 0; i < b; i++) {
        //이진탐색으로 A배열에 B[i]가 있는지 확인해서 1 출력
        if (binarySearch(A, 0, a - 1, B[i]) == 1)
            printf("1\n");
        else
            printf("0\n");

    }

    return 0;
}

int compare(const void * a, const void * b)
{
    return (*(int*)a - *(int*)b);
}
// 이진탐색 (탐색 후 있으면 return 1, 없으면 return 0)
int binarySearch(int* arr, int left, int right, int find) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == find) {
            return 1;
        }
        else if (arr[mid] < find) {
            left = mid + 1;
        }
        else if (arr[mid] > find) {
            right = mid - 1;
        }
    }
    return 0;

}

skdudn321 7년 전 2

compare 함수 작성을 잘못하신거 같습니다.

일반적인 경우 return (*(int*)a - *(int*)b); 에서도 잘 작동하지만

a - b가 int범위 값을 넘어가는 경우 정렬결과가 이상하게 나올수도 있습니다.

ex) a=20억 b=-20억

따라서 compare 함수를 return (*(int*)a > *(int*)b); 로 바꿔주시면 될 것 같습니다.

Conatuseus 7년 전 1

아하^^ deneb님,skdudn 님 감사합니다~!

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

문제

문제

출처

ICPC

계속 틀렸다고 나오네요...

Conatuseus 7년 전 0

deneb2016 7년 전 1

deneb2016 7년 전 2

skdudn321 7년 전 2

Conatuseus 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말