백준 알고리즘 11004번 : K번째 수

문제 링크

https://www.acmicpc.net/problem/11004

제한

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-10^9 ≤ Ai ≤ 10^9)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 및 출력

풀이

1. N의 최대 범위를 가지는 배열을 선언하면 정렬을 할 때 시간복잡도가 매우 커지기 때문에 동적할당을 사용했다.

2. N과 K그리고 N번 반복하여 수를 입력받는다.

3. stdlib.h라이브러리에 있는 정렬 함수인 qsort를 사용해서 오름차순 정렬을 진행한다.

4. K번째의 수를 출력한다.(인덱스 값이기 때문에 K - 1로 선언).

5. 마지막에 잊지 않고 동적으로 할당된 메모리를 free함수를 사용해서 해제한다.

풀이 코드

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

int compare(const void *a, const void *b){
  int num1 = *(int *)a;
  int num2 = *(int *)b;
  if (num1 < num2)    // a가 b보다 작을 때는
      return -1;      // -1 반환
  
  if (num1 > num2)    // a가 b보다 클 때는
      return 1;       // 1 반환
  
  return 0;    // a와 b가 같을 때는 0 반환
}

int main(){
  int n,k;
  scanf("%d%d",&n,&k);
  int *a = (int *)malloc(sizeof(int) * n);
  int arraySize = sizeof(a) / sizeof(int);
  for(int i = 0; i < n; i++){
    scanf("%d",&a[i]);
  }
  qsort(a, n, sizeof(int),compare);
  printf("%d\n",a[k -1]);
  free(a);
  return 0;
}

복기

원래 이 문제를 처음 풀었을 때는 버블 정렬(시간복잡도 : O(2^N))를 사용해서 문제를 풀었으나 시간초과로 인해 급하게 퀵정렬에 대해 찾아보고 풀었다.
정렬 알고리즘에 대해 배우고 정리할 시간이 된 것 같다.