글 읽기 - 1920번 질문입니다

wjdausrjf 10년 전 0

아래 코드가 틀렸습니다가 나오는 이유를 모르겠습니다 ㅠㅠ

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

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

int isthere(int arr[],int st,int ed,int num)
{
	int mid=(st+ed)/2;

	if(st>ed) return 0;

	if(arr[mid]==num) return 1;
	else if(arr[mid]>num) return isthere(arr,st,mid-1,num);
	else return isthere(arr,mid+1,ed,num);

}

int main(void)
{
	int N,*a,M,*b,i,j,tmp;

	scanf("%d",&N);
	a=(int*)malloc(sizeof(int)*N);
	for(i=0;i<N;i++){
		scanf("%d",&a[i]);
	}

	scanf("%d",&M);
	b=(int*)malloc(sizeof(int)*M);
	for(i=0;i<M;i++){
		scanf("%d",&b[i]);
	}

	qsort(a,N,sizeof(int),compare);

	for(i=0;i<M;i++){
		printf("%d\n",isthere(a,0,N-1,b[i]));
	}

}

hihihi 10년 전 0

정렬이 잘못되었나봅니다.

algorithm 헤더파일에 있는 std::sort를 쓰니까 맞네요 !

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

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

int isthere(int arr[],int st,int ed,int num)
{
    int mid=(st+ed)/2;

    if(st>ed) return 0;

    if(arr[mid]==num) return 1;
    else if(arr[mid]>num) return isthere(arr,st,mid-1,num);
    else return isthere(arr,mid+1,ed,num);

}

int main(void)
{
    int N,*a,M,*b,i,j,tmp;

    scanf("%d",&N);
    a=(int*)malloc(sizeof(int)*N);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }

    scanf("%d",&M);
    b=(int*)malloc(sizeof(int)*M);
    for(i=0;i<M;i++){
        scanf("%d",&b[i]);
    }

//    qsort(a,N,sizeof(int),compare);
    std::sort(a,a+N);
    for(i=0;i<M;i++){
        printf("%d\n",isthere(a,0,N-1,b[i]));
    }

}

wjdausrjf 10년 전 0

감사합니다 ㅠㅠ

WeissBlume 10년 전 3

qsort의 compare 함수를 짤 때, 뺄셈으로 짜는건 좋은 방법이 아닙니다..
예를 들어 -2000000000 에서 2000000000을 빼면 int의 범위를 넘어가버리기 때문에
제대로 된 값이 나오지 않기 때문이죠!
http://www.cplusplus.com/reference/cstdlib/qsort/?kw=qsort

Nada 10년 전 0

예전에 제가 그것 때문에 틀린 적이 있었는데 over flow 때문에
long long을 쓰시는 거나 algorithm 헤더에 있는 sort를 쓰시는 것이 좋습니다.

baekjoon 10년 전 2

qsort에서 사용하는 compare 함수의 리턴값은 큰 의미가 없고, 0보다 작냐, 크냐, 같냐가 의미가 있습니다.

따라서, 아래와 같이 작성하는 것이 좋습니다.

int compare(const void *a const void *b) {
	if (*(int *)a < *(int *)b) {
		return -1;
	} else if (*(int *)a == *(int *)b) {
		return 0;
	} else {
		return 1;
	}
}

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

문제

문제

출처

ICPC

1920번 질문입니다

wjdausrjf 10년 전 0

hihihi 10년 전 0

wjdausrjf 10년 전 0

WeissBlume 10년 전 3

Nada 10년 전 0

baekjoon 10년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말