3주년 문제 lecture note

  • sangchu
    sangchu

    2n 길이의 문자열을 2bytes씩 끊어서 알파벳 순으로 정렬하는 문제인데,
    1001byte 문자열에 값을 받아서 qsort로 정렬을 했습니다.

    그래서 만약 안된다면, TLE가 나올거라고 생각했는데 WA가 나오네요.
    예제는 잘 되었구요.

    그래서 input[500][3]으로 바꿔봤는데도 안되네요.
    문제될 것이 없어보이는데 안되는 이유가 뭔지 알고싶습니다.

    #include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
int compare(const void *, const void *); 
int main(int argc, char *argv[]) 
{ 
int test; 
char input[1001]; 

scanf("%d", &test); 
getchar(); 

while(test--){ 

gets(input); 

qsort(input, strlen(input) / 2, sizeof(char) * 2, compare); 

puts(input);
 } 
return 0; 

} 

int compare(const void *v1, const void *v2) 
{ return strcmp((char*)v1, (char*)v2); }

    14년 전
7개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    좀 위험한 구현인거 같은데, 만약에 문자열로 aaaaaaa.... 와 같은 입력이 들어올 경우 아래의 compare 함수가 제대로 동작하지 않을것 같은데요? 일단 compare 함수 내의 경우 strcmp의 경우 null character 처리가 되지 않은 문자열에 대해서는 오작동을 일으킬 가능성이 많아보입니다.


    14년 전 link
  • VOCList
    VOCList

    AOJ 저지머신과 같은 리눅스계열 OS에서는 잘 안돌아갈거같네요.


    14년 전 link
  • sangchu
    sangchu

    흠.. 일단 입력이 소문자로만 제한을 해서 null에 대한 처리를 안했구요. aaaaaaaa.. 같은 경우는 같으면 0을 리턴하니 아무런 처리를 안하고 넘어가지 않을까요?


    14년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    알고리즘의 문제가 아니라 입력받는 방식의 문제네요.
    scanf("%d", &test);
    getchar();
    while(test--){
    이런 식으로 받으시면 안 됩니다..

    줄바꿈 문자가 '\n' 라는 보장이 없어요..
    위 부분을 if (getchar() == '\r') while(1);
    이런 식으로 바꿔보니까 TLE가 나네요.
    줄바꿈 문자가 \r\n 인가 봅니다.

    근데 사실 그것보다도..
    왜 scanf("%s",input); 을 안 쓰셨는지 궁금하네요..


    14년 전 link
  • Being
    Being

    일단 같으면 0 리턴과 별개로.. strcmp가 '\0'이 나올때까지 비교하기 때문에 별로 좋은 구현은 아닌 것 같습니다. 물론 이 문제의 경우는 잘 작동하겠지만요.


    14년 전 link
  • JongMan
    JongMan

    곰곰이 생각해봤는데 뻑날 가능성도 있는거 같습니다.

    strncmp 를 쓰시는 게 아니라 strcmp 를 쓰시니까 두 문자열이 같은 경우 뒤에 무엇이 따라오느냐에 따라 답이 달라지는데요.. 그러면 같은 aa < aa > aa 뭐 이런 식의 결과를 compare() 함수가 반환하게 됩니다. qsort() 는 비교 함수의 결과가 일관성 있다는 전제 하에 구현되었기 때문에 경우에 따라서는 뻑날수도 있겠네요~

    이런 핵 대신에 더 좋은 구현 방법을 고민해 보시는 건 어떨까요.


    14년 전 link
  • sangchu
    sangchu

    아.. scanf를 왜 생각못했을까.. 이제 되네요. 이런 사소한 것들을 자꾸 놓치네요. 답변 주신분들 감사합니다.


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.