글 읽기 - 시간초과가 뜨네요

noel7781 6년 전 0

퀵소트를 써서 문제를 풀려고했는데 시간초과 에러가 뜨네요.

어디를 손봐야 할까요?

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

typedef struct people {
    char name[21];
}People;

void nameSort(People list[], int left, int right);
void swap(People* a, People* b);


int main() {
    int dp, bp;
    int total;
    int small;
    int size = 0;
    int i, j, k;
    scanf("%d %d", &dp, &bp);
    if(dp > bp) small = bp;
    else small = dp;
    People* Dp = (People*)malloc(sizeof(People) * dp);
    People* Bp = (People*)malloc(sizeof(People) * bp);
    People* result = (People*)malloc(sizeof(People) * small);
    total = dp + bp;
    for(i = 0; i < dp; i++) {
        scanf("%s", Dp[i].name);
    }
    nameSort(Dp, 0, dp - 1);
    for(i = 0; i < bp; i++) {
        scanf("%s", Bp[i].name);
    }
    nameSort(Bp, 0, bp - 1);
    i = 0, j = 0, k = 0;
    while((i != dp) && (j != bp)) {
        if(strcmp(Dp[i].name, Bp[j].name) == 0) {
            strcpy(result[size++].name, Dp[i].name);
            i++;
            j++;
        } else if(strcmp(Dp[i].name, Bp[j].name) < 0) {
            i++;
        }
        else {
            j++;
        }
    }
    printf("%d\n", size);
    for(i = 0; i < size; i++) {
        printf("%s\n", result[i].name);
    }
    free(Dp);
    free(Bp);
    free(result);
}

void nameSort(People list[], int left, int right) {
    int i, j;
    char *pivot;
    People temp;
    if(left < right) {
        i = left; j = right + 1;
        pivot = list[left].name;
        do {
            do {
                i++;
            }while(strcmp(list[i].name, pivot) < 0 && i < right);
            do {
                j--;
            }while(strcmp(list[j].name, pivot) > 0 && j >= left);
            if(i < j) {
                swap(&list[i], &list[j]);
            }
        }while(i < j);
        swap(&list[left], &list[j]);
        nameSort(list, left, j - 1);
        nameSort(list, j + 1, right);
    }
}

void swap(People* a, People* b) {
    People temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

chogahui05 6년 전 0

left를 기준으로 pivot을 잡는 방법을 택하셨는데요~

이런 경우에 시간 초과가 걸리겠죠.

/*
aaa
aab
aac
aad
...
*/

noel7781 6년 전 0

그럼 소팅방법을 바꿔야되나요? merge sort 같은걸 써야 하나요??

chogahui05 6년 전 0

그러셔도 되고요. 애초에 Merge는

분할하고 합병하는 과정이 있으니.. 대충 n짜리 data에 대해서

(1) n/2짜리 2개로 나누고

(2) n/2짜리를 정렬하고 T(n/2)

(3) 순서 맞춰주고 = n

이여서 T(n) = 2T(n/2) + n이 되고요.

이걸 좌르륵 풀어주면 T(n) = 2(2*T(n/4) + n/2) + n

= 4*T(n/4) + 2n

= 4*(2T(n/8) + n/4) + 2n

= 8T(n/8) + 3n

...

이렇게 전개가 되기 때문에 O(nlogn)쯤 되는 게 맞고요.

아니면 퀵 sort를 하는데, 중위법으로 pivot을 택하는 방법도 있습니다.

간단하게 설명하면

left, right, mid값들을 가져와서, 그것의 중간값을 pivot으로 취해주겠다는 겁니다.

https://stackoverflow.com/ques...

noel7781 6년 전 0

감사합니다 다시해볼게요

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

문제

문제

출처

ICPC

시간초과가 뜨네요

noel7781 6년 전 0

chogahui05 6년 전 0

noel7781 6년 전 0

chogahui05 6년 전 0

noel7781 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말