글 읽기 - 어떤 반례가 있는지 모르겠습니다.

amazon297 1년 전 0

어디가 틀린 건지 도무지 모르겠습니다. 도와주세요.

#include <stdio.h>
#include <stdlib.h>
int compare(const void *p,const void *q) 
{
    if (*(int *)p > *(int *)q)
        return 1;
    else if (*(int *)p < *(int *)q)
        return -1; 
    else
        return 0;
}
int main(void)
{
    int N,M,k;
    scanf("%d",&N);
    int *A = (int *)calloc(N+1,4);
    for (register int i=1;i<=N;i++)
        scanf("%d",A+i);
    qsort(A+1,N,4,compare);
    scanf("%d",&M);
    for (register int i=0;i<M;i++)
    {   
        scanf("%d",&k);
        if ((A[1] <= k) && (k <= A[N]))
            printf("1\n");
        else
            printf("0\n");
    }   
    return 0;
}

w8385 1년 전 1

문제에서 요구하는 바를 다시 확인해보세요.

A[1] <= x <= A[N] 인 x인지를 확인하는 것이 아니라,

N개의 정수와 M개의 정수끼리 정확히 일치하는 지를 판단하는 문제입니다.

amazon297 1년 전 0

아래코드로 고쳤는데 시간초과가 나는데 혹시 시간초과가 안나오도록 하는 방법도 알려주실 수 있나요?

#include <stdio.h>
#include <stdlib.h>
int compare(const void *p,const void *q) 
{
    if (*(int *)p > *(int *)q)
        return 1;
    else if (*(int *)p < *(int *)q)
        return -1; 
    else
        return 0;
}
int main(void)
{
    int N,M,k,r;
    scanf("%d",&N);
    int *A = (int *)calloc(N+1,4);
    for (register int i=1;i<=N;i++)
        scanf("%d",A+i);
    qsort(A+1,N,4,compare);
    scanf("%d",&M);
    for (register int i=0;i<M;i++)
    {   
        scanf("%d",&k);
        if ((A[1] <= k) && (k <= A[N]))
        {
            for (r=1;r<=N;r++)
                if (A[r] == k)
                {
                    printf("1\n");
                    break;
                }
            if ((r==N) && (A[N] != k)) 
                printf("0\n");
        }
        else
            printf("0\n");
    }   
    return 0;
}

w8385 1년 전 0

올려주신 코드의 시간 복잡도는 O(N*M)입니다.

N과 M이 각각 10^5이기에 시간초과가 발생합니다.

보다 빠르게 확인할 수 있는 이진탐색 혹은 적절한 자료구조를 적용하셔야합니다.

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

문제

문제

출처

ICPC

어떤 반례가 있는지 모르겠습니다.

amazon297 1년 전 0

w8385 1년 전 1

amazon297 1년 전 0

w8385 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말