Baekjoon 10815. 숫자 카드

nang_nang·2022년 11월 23일
0

PS

목록 보기
7/18

📝 Baekjoon 10815 문제풀이


💡문제 정의

baekjoon 10815


문제는 위와 같다.
input의 크기가 최대 500,000까지 될 수 있기 때문에 시간 복잡도가 O(N^2)인 알고리즘으로 해결할 수 없고, O(NlogN)으로 구현해야 한다.
즉 Binary Search(이진 탐색)를 사용해 해결하면 되는 문제이다.

Binary Search를 구현하기 위해서는

*** 탐색하는 배열이 정렬되어 있어야 한다!!! (sorted array에서만 Binary Search 수행 가능)

처음에 이 사실을 망각하고, 배열을 정렬하지 않은 채 코드를 구현했더니 잘못된 답이 나왔다. 그래서 배열을 정렬하는 코드를 추가한 후 문제를 해결할 수 있었다.

배열 정렬을 구현하는 과정에서, 정렬 코드를 직접 다 구현해야 하나...? 싶어서 구글링을 해봤다. 이 과정에서 stdlib.h 헤더파일에 있는 qsort 함수의 존재를 알게 되었다.


🚀 qsort

qsort는 stdlib.h 헤더파일에서 제공하는 Quick sort를 수행하는 함수이며, 함수의 프로토타입은 아래와 같다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *)
  • 리턴타입 : void
  • 파라미터 : 배열, 배열의 길이(배열 요소의 개수), 배열 요소의 크기, 비교를 수행할 함수의 포인터(함수 포인터)
  • 리턴값 : 없음

여기서 4번째 parameter인 비교 함수는 요소 2개의 크기를 비교하는 함수로, 배열을 오름차순으로 정렬할 것이냐, 내림차순으로 정렬할 것이냐에 따라 달라진다. 만약 오름차순으로 정렬할 것이라면 아래와 같이 구현하면 되고, 내림차순으로 정렬할 것이라면 1번과 3번의 부등호 방향을 반대로 하면 된다.

(오름차순 정렬일 때)
1. 요소1 > 요소2: 양수 반환
2. 요소1 == 요소2: 0 반환
3. 요소1 < 요소2: 음수 반환

위와 같이 양수/0/음수 중 하나를 반환하도록 작성해야 한다.

qsort 함수를 통한 quick sort 구현

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

// 오름차순 정렬 
int compare(const void *first, const void *second) {
  return *((int *)first) - *((int *)second);
}

int main(void) {
  int arr[10] = {10, 20, 2, 4, 22, 33, 15, 9, 80, 50};

  printf("before sorting: \n");
  for (int i = 0;i < 10;i++) printf("%d ", arr[i]);
  printf("\n");

  qsort(arr, 10, sizeof(int), compare);

  printf("after sorting: \n");
  for (int i = 0;i < 10;i++) printf("%d ", arr[i]);
  printf("\n");

  return 0;
}


위는 quick sort 코드 실행 결과이다.


qsort 함수를 활용하여 가지고 있는 숫자 카드를 정렬한 후 Binary Search를 수행했다.

1) C

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

int card[500000];

int compare(const void *first, const void *second) {
  return *((int *)first) - *((int *)second);
}

int main(void) {
  int N, M;
  scanf("%d", &N);
  for (int i = 0;i < N;i++) scanf("%d", &card[i]);
  
  qsort(card, N, sizeof(int), compare);

  scanf("%d", &M);

  for (int i = 0;i < M;i++) {
    int target;
    scanf("%d", &target);
    int res = 0;
    int l = 0, r = N - 1;
    while (l <= r) {
      int mid = l + (r - l) / 2;
      if (card[mid] == target) {
        res = 1;
        break;
      }
      else if (card[mid] > target) r = mid - 1;
      else l = mid + 1;
    }
    printf("%d ", res);
  }

  return 0;
}

💡참고

https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort?view=msvc-170&viewFallbackFrom=vs-2019
https://norux.me/10
https://twpower.github.io/56-qsort-in-c

profile
조금씩 앞으로

0개의 댓글