백준/11004 K번째 수

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: K번째 수 문제는 MergeSort를 활용해 풀 수 있다.

  • 범위가 500만이기 때문에 O(n^2) 시간복잡도로는 해결할 수 없다.

  • 따라서 O(nlogn) 시간복잡도인 QuickSort와 MergeSort를 사용해야 하는데 평균 O(nlogn)인 MergeSort를 사용했다.

  • MergeSort 작동 방식
    1. 현재 배열 num과 임시 배열 tmp를 파라미터로 넘긴다.
    2. start < end 가 아닐 경우까지 쪼갠다.
    3. 다 쪼개졌다면 MergeSort 함수로 넘어간다.
    4. num 배열을 tmp 배열에 옮긴다.
    5. tmp 배열의 left, right 인덱스를 비교하면서 num 배열에 저장한다.
    6. while문을 통해 남아있는 배열을 num 배열에 옮긴다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] num, tmp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());
        num = new int[n];
        tmp = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(stk.nextToken());
        }
        merge(0, n - 1);
        System.out.println(num[k - 1]);
    }

    public static void merge(int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            merge(start, mid);
            merge(mid + 1, end);
            mergeSort(start, mid, end);
        }
    }

    public static void mergeSort(int start, int mid, int end) {
        for (int i = start; i <= end; i++) {
            tmp[i] = num[i];    //tmp 배열에 값을 옮긴다.
        }
        int left = start;
        int right = mid + 1;
        int idx = start;
        while (left <= mid && right <= end) {
            //num 배열에 비교하면서 저장
            if (tmp[left] >= tmp[right]) {
                num[idx++] = tmp[right++];
            } else {
                num[idx++] = tmp[left++];
            }
        }
        //어느 한쪽에 남은 tmp 배열을 num 배열에 저장
        while (left <= mid) num[idx++] = tmp[left++];
        while (right <= end) num[idx++] = tmp[right++];
    }
}