글 읽기 - 1181 단어 정렬 : C 왜 시간초과가 발생하는지 궁금합니다.

qotmd01 2년 전 0

우선 단어 알파벳수를 기준으로 퀵정렬하였고,

while문으로 알파벳수가 같은 단어를 찾아 그 단어들 끼리 안에서 사전순으로 퀵정렬을 하였습니다.

그런데 시간초과가 발생한다고 하는데 이유를 알 수 있을까요?

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

int Arr[51];
char charArr[20001][51];
void Quicksort(int *data,int start,int end);
void QuicksortArray(int start,int end);
void cswap(char *x, char *y){
    char temp[101];
    char temp2[101];
    strcpy(temp, x);
    strcpy(temp2,y);
    strcpy(x, temp2);
    strcpy(y, temp);
}
void iswap(int *data,int x, int y){
    int temp;
    temp = data[x];
    data[x] = data[y];
    data[y] = temp;
}
int main(){
    int TestCase;
    scanf("%d",&TestCase);
    for (int i = 0; i < TestCase; i++) {
        scanf("%s",&charArr[i]);
        Arr[i] = strlen(charArr[i]);
    }
    Quicksort(Arr,0,TestCase-1);
    

    int j,count = 0, count2 = 0;
    while (count < TestCase - 1) {   // 글자수 같은 단어끼리 퀵정렬하기
        j = count;
        while (Arr[j] == Arr[j + 1]) {
            count2 += 1;
            j += 1;
            /*if (j == TestCase-1) {
                break;
            }*/
        }
        if (count2 != 0) {
            //printf("%d %d\n",count,count + count2);
            QuicksortArray(count, count + count2);
            count += count2;
            count2 = 0;
        }
        else{
            count += 1;
        }


    }
    //int k,new_count = 0 , count3 = 0;
    
    for (int i = 0; i < TestCase; i++) {
        if (strcmp(charArr[i], charArr[i+1]) == 0) {
            continue;
        }
        else{
            printf("%s\n",charArr[i]);
        }
    }

}


void Quicksort(int *data, int start,int end){  // 단어수 퀵정렬
    if (start >= end) {
        return;
    }
    int key = start;
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (data[key] >= data[i]) {
            i++;
        }
        while (data[key] <= data[j] && j > start) {
            j--;
        }
        if (i > j) {
            iswap(data, key, j);
            cswap(charArr[key], charArr[j]);
        }
        else{
            iswap(data, i, j);
            cswap(charArr[i],charArr[j]);

        }
    }
    Quicksort(data,start, j-1);
    Quicksort(data,j+1, end);
}

void QuicksortArray(int start,int end){   // 사전 퀵정렬
    if (start >= end) {
        return;
    }
    int key = start;
    int i = start + 1;
    int j = end;
    while (i <= j) {
        while (strcmp(charArr[key],charArr[i]) >= 0) {
            i++;
        }
        while (strcmp(charArr[key] , charArr[j]) <= 0 && j > start) {
            j--;
        }
        if (i > j) {
            iswap(Arr, key, j);
            cswap(charArr[key], charArr[j]);
        }
        else{
            iswap(Arr, i, j);
            cswap(charArr[i],charArr[j]);

        }
    }
    QuicksortArray(start,j-1);
    QuicksortArray(j+1, end);
}

djm03178 2년 전 0

퀵소트는 버블 정렬과 같은 O(N^2)이기 때문에 너무 느립니다. 병합 정렬 등의 O(NlogN)의 정렬을 사용하세요.

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

문제

문제

출처

ICPC

1181 단어 정렬 : C 왜 시간초과가 발생하는지 궁금합니다.

qotmd01 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말