글 읽기 - [C99][스포] 1764 듣보잡 동적할당 & qsort 안되시는분!

wnstjd732 1년 전 1

[[일단 1줄 요약]]

1. qsort의 compare 함수가 잘못되었을 확률이 있다!
__________________________________________________________________

안녕하세요,,, 듣보잡 한 며칠 동안 골머리 앓다가 이것저것 시도해보다 알아낸 바보 같은 사실 알려드리려 글 써봅니다

일단, 저는 문제에서 N과 M이 500,000 이상이라고 해서, 동적할당으로 접근했어요. (원래 의도한 풀이 방식도 이거같음)

그래서 배열 동적할당 해주고,,

char *lis[500000];

for(int i=0; i<N; i++){

lis[i] = (char *)calloc(21, sizeof(char));

scanf("%s", lis[i]);

}

배열 compare 함수를 선언해줬는데..!

int compare(void *first, void *second){

return strcmp((char*)first, (char*)second);

}

안되는거에요! 근데 사실은...

int compare(void *first, void *second){

return strcmp(*(char**)first, *(char**)second);

}

이렇게 하니까 해결되더라구요? (이것도 잘 모르겠음)

일단.... 왜인진 모르겠지만 일단 해결되었으니,, OK라는 생각입니다!

안되시는분은 참고해주시고 혹시 이 동작원리를 아시는분은 설명 가능할까요..?!

원본 코드 첨부합니당

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(void* first, void* second){
  return strcmp(*(char**)first, *(char**)second);
}
int main(){
  int N, M, result = 0;
  char *lis[500000], see[21];
  scanf("%d %d", &N, &M);
  for(int i=0; i<N; i++){
    lis[i] = (char *)calloc(21, sizeof(char));
    scanf("%s", lis[i]);
  }
  qsort(lis, N, sizeof(lis[0]), compare);
  for(int i=0; i<M; i++){
    int min=0, mid=N/2, max=N-1;
    scanf("%s", see);
    for(;min<=max;mid=(min+max)/2){
      int cmp = strcmp(see, lis[mid]);
      if(cmp == 0){
        result++;
        lis[mid][20] = 1;
        break;
      }
      else if(cmp<0)
        max = mid-1;
      else
        min = mid+1;
    }
  }
  printf("%d\n", result);
  for(int i=0; i<N; i++){
    if(lis[i][20] == 1){
      lis[i][20] = 0;
      printf("%s\n",lis[i]);
    }
  }
}

jdeokkim 1년 전 2

`qsort()`의 비교 함수의 인수로 전달되는 값은 정렬할 원소의 메모리 주소입니다. 그렇기 때문에 `int` 값의 배열을 정렬하고자 한다면 `const int *`가 비교 함수의 인수로 전달되는 것이고, `char *` 값의 배열을 정렬하고자 한다면 `const char **`가 비교 함수의 인수로 전달되는 것입니다.

qsort, qsort_s - cppreference.com

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

int compare_values(const void *a, const void *b) {
    // `a`와 `b`가 배열의 원소를 가리키는 포인터임에 주의!
    int x = *(const int *) a;
    int y = *(const int *) b;

    return (x > y) - (x < y);
}

int main(void) {
    int values[] = { -3, 10, 5, 2, 13 };

    size_t len = sizeof(values) / sizeof(*values);

    qsort(values, len, sizeof(*values), compare_values);

    for (int i = 0; i < len; i++) 
        printf("%d ", values[i]);
    
    printf("\n");

    return 0;
}

wnstjd732 1년 전 1

감사드립니다..! 모호했던 포인터 개념때문에 일어난 일이었네요 ㅎㅎㅎ...

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