글 읽기 - [c] 정렬과 투포인터로 풀었어요

mun9769 3년 전 0

33줄까지는 병합정렬에 대한 코드입니다

두 배열을 크기순서대로 정렬한 다음에 같은 숫자가 있다면 res배열에 체크하는 식으로 짰습니다.

#include <cstdio>
#include <cstdlib>

static int *buff;
int a[100005];
int b[100005];
int copyB[100005];
int res[100005];

void __merge(int *a, int left, int right)
{
    if(left < right)
    {
        int i, j=0, p=0;
        int k=left;
        int center = (left+right) / 2;
        __merge(a,left,center);
        __merge(a,center+1, right);
        for(i=left; i<=center; i++)
            buff[p++] = a[i];
        while(j<p && i<=right)
            a[k++] = buff[j] <= a[i] ? buff[j++] : a[i++];
        while(j<p)
            a[k++] = buff[j++];
    }
}

void mergesort(int *a, int n)
{
    buff = (int*)malloc(sizeof(int)*n);
    __merge(a,1,n);
    free(buff);
}

int main()
{
    int n, m, pa = 1, pb = 1;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    for(int i=1; i<=m; i++){
        scanf("%d", &b[i]);
        copyB[i] = b[i];
    }
    mergesort(a, n);
    mergesort(b, m);

    while(1)
    {
        if(pa > n || pb > m) break;
        
        if(a[pa] < b[pb]) pa++;
        else if (a[pa] > b[pb]) pb++;
        else
        {
            for(int i=1; i<=m; i++)
                if(copyB[i] == b[pb]) {
                    res[i] = 1;
                    break;
                }
            pa++;
            pb++;
        }
    }
    for(int i=1; i<=m; i++)
        printf("%d\n", res[i]);
        
    return 0;
}

flappybird 3년 전 2

60줄에 하나의 맞는 쌍을 찾았다고 for문을 나와버리면 맞는 쌍이 여러개인경우(두번째 배열에 같은 두 값이 존재하는 경우)를 찾지 못하게 됩니다.

또한 제한이 그렇게 크지 않아서 하나의 수가 있는지 없는지 이분탐색으로 체크해도 충분히 시간제한 내에 돌아갈것같네요.

//in
5
1 2 3 4 5
5
1 1 2 2 3

//output
1
0
1
0
1

//answer
1
1
1
1
1

mun9769 3년 전 0

감사합니다 중복된 수에 대해 생각해보지 못했네요

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

문제

문제

출처

ICPC

[c] 정렬과 투포인터로 풀었어요

mun9769 3년 전 0

flappybird 3년 전 2

mun9769 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말