글 읽기 - c언어 1181번 시간초과 뭐가 잘못된걸 까요 ㅠㅠ

kjk0385 2년 전 0

합병정렬을 사용하였는데도 시간초과 오류가 납니다 ㅠㅠ 어느 부분을 고쳐야 할까요.....

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
void merge(char **a, int low, int mid, int hight);
void mergesort(char **a, int low, int hight);
int main(void) {
    int n;//입력받을 단어의 개수.
    char* tmp = NULL;
    scanf("%d", &n);
    char **arr = (char**)malloc(sizeof(char*) * n);//2차원 동적배열할당 
    for (int i = 0; i < n; i++) {
        arr[i] = (char*)malloc(sizeof(char) * 51);
    }
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    mergesort(arr, 0, n-1);//사전순 정리

    for (int i = 0; i < n; i++) {//길이가 짧은대로 정렬 
        for (int j = 0; j < n -1-i; j++) {
            if (strlen(arr[j]) > strlen(arr[j + 1])) {
                tmp = arr[j + 1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
                tmp = NULL;
                
            }
        }
    }
    tmp = NULL;
 



    for (int i = 0; i < n; i++) {//중복되는 문자열 제거
        if (i == n - 1) 
            printf("%s", arr[i]);
        else if (strcmp(arr[i], arr[i + 1]) == 0) 
            ;
        
        else
            printf("%s\n", arr[i]);
        
    }
    for (int i = 0; i < n; i++) {
        free(arr[i]);
    }
    free(arr);
    return 0;
}
void merge(char** a, int low, int mid, int hight)//hight=n-1 low =0
{
    char** b = NULL;
    b = (char**)malloc(sizeof(char*) * (hight + 1));
    for (int i = 0; i < (hight+1); i++) {
        b[i] = (char*)malloc(sizeof(char) * 51);
    }

    int i = low;
    int j = mid + 1;
    int k = 0;//b의 현재 인덱스 값 

    while (i <= mid && j <= hight) {
        if (strcmp(a[i], a[j]) <= 0)
            strcpy(b[k++], a[i++]); //b[k++] = a[i++];
        else
            strcpy(b[k++], a[j++]);//b[k++] = a[j++];
        
    }

    while (i <= mid)
        strcpy(b[k++], a[i++]);//b[k++] = a[i++];
    while (j <= hight)
        strcpy(b[k++], a[j++]);//b[k++] = a[j++];
    k--;//k=hight

    while (k >= 0) {
        strcpy(a[low+k],b[k]);// a[low + k] = b[k];
        k -- ;
    }
 
    
    for (int i = 0; i < (hight + 1); i++) {
        free(b[i]);
    }
    free(b);
   
}
void mergesort(char** a, int low, int hight)
{
    int mid;
    if (low < hight)
    {
        mid = (low + hight) / 2;
        mergesort(a, low, mid);
        mergesort(a, mid + 1, hight);
        merge(a, low, mid, hight);
    }
}