BOJ_11004 : K번재 수

👉 문제링크

11004번: K번째 수

---

---

🔸 문제 분석 🔸

• 입력받은 N개의 수를 오름차순으로 정렬했을때 K번재 수를 출력한다.
• N이 최대 5,000,000(5백만)이므로, O(nlogn)은 약 3천만이 나온다.
  • 일반적인 정렬 알고리즘의 평균 시간 복잡도가 O(nlogn)이므로, 제한시간 2초안에 든다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int arr[] = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        System.out.println(arr[k-1]);
    }
}

🔸 코드 해석 🔸

• n개의 수를 입력받아 배열 arr에 저장한다.
• 배열 arr를 Arrays.sort()를 사용해 오름차순 정렬한다.
• 배열 arr의 k번째 수를 출력한다.

---

🔸 end 🔸

• 결과적으로 최종 코드에서 아주 단순한 배열 오름차순 정렬을 사용해도 통과했지만,
  O(n^2)인 경우가 있을까봐 카운트 정렬를 써야되는 줄 알고 오답이 늘었다.
  • 이 문제에서 O(n^2)이면, 25,000,000,000,000(25조)이므로 제한시간을 훨씬 넘게된다.
  • 따라서 연산 횟수를 줄이기 위해 카운트 정렬을 사용하려고 했다.
  • 하지만 수의 범위가 -10^9 ~ 10^9 이므로 자바의 배열 범위를 넘게되서 불가능했다.
  • 알아보니 이 문제는 N개의 수에서 K번째 수를 반환하는 경우에 사용되는 특정한 알고리즘인
    Quick Selection 알고리즘을 사용할 수 있다고 한다. Quick sort방식을 응용한 방식이다.