글 읽기 - 1181번 C언어 질문 드립니다.

akrnrnak9 3년 전 0

힙정렬을 이용해서 구현했습니다.

컴파일 잘 되고, 실행도 잘 됩니다.

어떤 스페셜케이스에서 비정상적인 출력을 하는 것 같은데, 도통 이유를 모르겠습니다.

몇시간동안 보고 있어서 머리 깨질 것 같습니다 ㅠㅠ 많은 도움 주시면 감사하겠습니다!

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

#define SIZE 20001

typedef struct
{
    char *heap[SIZE];
    int heap_size;
} Heap;

void create(Heap **h)
{
    *h = malloc(sizeof(Heap));
}

void init(Heap *h)
{
    h->heap_size = 0;
}

void insert_min_heap(Heap *h, char *word)
{
    int i;

    for(i = ++(h->heap_size); i != 1 && (strlen(word) <= strlen(h->heap[i / 2])); i /= 2)
        if(strlen(word) == strlen(h->heap[i / 2]))
        {
            if(strcmp(word, h->heap[i / 2]) == -1)
                h->heap[i] = h->heap[i / 2];
            else
                break;
        }
        else
            h->heap[i] = h->heap[i / 2];
    h->heap[i] = word;
}

char *delete_min_heap(Heap *h)
{
    char *tmp = h->heap[1], *key = h->heap[h->heap_size--];
    int parent = 1;

    for(int child = 2; child <= h->heap_size; parent = child, child *= 2)
    {
        if(child < h->heap_size && strlen(h->heap[child]) >= strlen(h->heap[child + 1]))
        {
            if(strlen(h->heap[child]) > strlen(h->heap[child + 1]))
                child++;
            else
                if(strcmp(h->heap[child], h->heap[child + 1]) == 1)
                    child++;
        }

        if(strlen(h->heap[child]) <= strlen(key))
        {
            if(strlen(h->heap[child]) < strlen(key))
                h->heap[parent] = h->heap[child];
            else
                if(strcmp(h->heap[child], key) == -1)
                    h->heap[parent] = h->heap[child];
                else
                    break;
        }
        else
            break;
    }
    h->heap[parent] = key;

    return tmp;
}

int main(void)
{
    Heap *h;
    int N;
    char **arr;

    create(&h);
    init(h);

    scanf("%d", &N);

    arr = (char **)malloc(sizeof(char *) * N);
    for(int i = 0; i < N; i++)
        arr[i] = malloc(sizeof(char) * 51);
        
    for(int i = 0, flag = 0; i < N; i++, flag = 0)
    {
        scanf("%50s", arr[i]);
        for(int j = 1; j <= h->heap_size; j++)
            if(!strcmp(h->heap[j], arr[i]))
            {
                flag = 1;
                break;
            }
        
        if(!flag)
            insert_min_heap(h, arr[i]);
    }

    for(int i = 0, count = h->heap_size; i < count; i++)
        printf("%s\n", delete_min_heap(h));

    return 0;
}

slah007 3년 전 0

다음과 같은 입력을 고려해보세요.

또한 정렬 로직 이외에 Heap->heap[] 도 malloc으로 할당이 필요할 것 같습니다.

akrnrnak9 3년 전 0

의 입력도 a, i순으로 잘 나옵니다. Heap->heap[]도 malloc으로 할당을 해보았는데, 여전히 문제가 있나봅니다ㅠㅠ

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

#define SIZE 20001

typedef struct
{
    char *heap[SIZE];
    int heap_size;
} Heap;

void create(Heap **h)
{
    *h = malloc(sizeof(Heap));
}

void init(Heap *h)
{
    h->heap_size = 0;
}

void insert_min_heap(Heap *h, char *word)
{
    int i;

    for(i = ++(h->heap_size); i != 1 && (strlen(word) <= strlen(h->heap[i / 2])); i /= 2)
        if(strlen(word) == strlen(h->heap[i / 2]))
        {
            if(strcmp(word, h->heap[i / 2]) == -1)
                h->heap[i] = h->heap[i / 2];
            else
                break;
        }
        else
            h->heap[i] = h->heap[i / 2];
    h->heap[i] = word;
}

char *delete_min_heap(Heap *h)
{
    char *tmp = h->heap[1], *key = h->heap[h->heap_size--];
    int parent = 1;

    for(int child = 2; child <= h->heap_size; parent = child, child *= 2)
    {
        if(child < h->heap_size && strlen(h->heap[child]) >= strlen(h->heap[child + 1]))
        {
            if(strlen(h->heap[child]) > strlen(h->heap[child + 1]))
                child++;
            else
                if(strcmp(h->heap[child], h->heap[child + 1]) == 1)
                    child++;
        }

        if(strlen(h->heap[child]) <= strlen(key))
        {
            if(strlen(h->heap[child]) < strlen(key))
                h->heap[parent] = h->heap[child];
            else
                if(strcmp(h->heap[child], key) == -1)
                    h->heap[parent] = h->heap[child];
                else
                    break;
        }
        else
            break;
    }
    h->heap[parent] = key;

    return tmp;
}

int main(void)
{
    Heap *h;
    int N;
    char **arr;

    create(&h);
    init(h);

    scanf("%d", &N);

    arr = (char **)malloc(sizeof(char *) * N);
    for(int i = 0; i < N; i++)
    {
        arr[i] = malloc(sizeof(char) * 51);
        h->heap[i] = malloc(sizeof(char) * 51);
    }
    h->heap[N] = malloc(sizeof(char) * 51);
        
    for(int i = 0, flag = 0; i < N; i++, flag = 0)
    {
        scanf("%50s", arr[i]);
        for(int j = 1; j <= h->heap_size; j++)
            if(!strcmp(h->heap[j], arr[i]))
            {
                flag = 1;
                break;
            }
        
        if(!flag)
            insert_min_heap(h, arr[i]);
    }

    for(int i = 0, count = h->heap_size; i < count; i++)
        printf("%s\n", delete_min_heap(h));

    return 0;
}

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

문제

문제

출처

ICPC

1181번 C언어 질문 드립니다.

akrnrnak9 3년 전 0

slah007 3년 전 0

akrnrnak9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말