🔍 Problem

백준 11004 K번째 수 구하기

---

📃 Input&Output

---

🌁 문제 배경

가. 문제 설명
정렬 문제이다. 하지만 필자는 퀵정렬을 학습하고자, 퀵정렬을 구현하였다.

나. 접근 방법

다. 문제 유형

---

📒 수도 코드

가. 퀵정렬을 한다.
🔥 퀵정렬이란?
나. 정렬된 배열에서 첫번째 입력 줄의 두번째 입력값을 idx로 하는 원소를 출력한다.

---

💻 Code

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class P19 {

    static void quickSort(int[] arr){
        if(arr.length==1){
            return;
        }
        quickSort(arr, 0, arr.length-1);
    }

    static void quickSort(int[] arr, int start, int end) {
        int part2 = partition(arr,start,end); // part2 : 두번째 배열의 첫번째 idx
        if(start+1<part2){
            quickSort(arr,start,part2-1);
        }
        if(part2<end){
            quickSort(arr,part2,end);
        }

    }
    static int partition(int[] arr, int start, int end){
        int pivot = arr[(start+end)/2];

        while(start<=end){
            while(arr[start]<pivot) start++;
            while(arr[end]>pivot) end--;
            if(start<=end){
                swap(arr, start, end);
                start++;
                end--;
            }
        }

        return start;       // 두 번째 파티션의 첫 번째 index를 결국 start가 end를 넘어서 반환
    }

    static void swap(int[] arr, int start, int end){
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = 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());
        }
        quickSort(arr);
        bw.write((arr[M-1])+"");

        bw.flush();
        bw.close();

    }
}

---

🤔 느낀점

	Arrays.sort()	Collections.sort()
알고리즘 이름	DualPivotQuicksort	TimeSort(삽입정렬+병합정렬)
시간복잡도	평균 : O(nlogn), 최악 : O(n^2)	All : O(nlogn)

List정렬이 배열 정렬보다 더 안전하다고 한다. 그렇다면 배열을 리스트로 바꾸는 방법은 무엇일까

int[] arr = new int[]{1,2,4,1,2};
List<Integer> list = Arrays.stream(arr).boxed().toList()

Integer[] arr = ~;
list = Arrays.asList(arr);

결국 List는 래퍼클래스 자료형이 필요했던 것이다.