[JAVA] 백준 11004번 【K번째 수】

---

이 문제는, BufferedReader 로 입력 받고, sort() 메서드를 쓰면 해결되긴 하지만, 정렬 알고리즘 유형 특성상, 정렬을 구현하게끔 설계해놨을 것이라 생각이 들기도 했고, 속도도 느린 것 같아 찾아보니 

 

Quick Sort 알고리즘을 이용해서 푸는 사람들이 많았다.

 

double pivot quick sort 라는 quick sort 의 다른 버전도 있었지만, 

 

Quick sort 자체를 처음 접해봐서, 일단 Quick Sort 를 공부해보고 코드를 작성하여 제출하였다.

 

오름차순 기준으로 설명해보겠다.

 

간단하게 설명하면, 기준 값을 하나 정하고, start index 0에서부터 기준값보다 크거나 값을 발견하고, end index 끝에서부터 기준값보다 작거나 같은 값을 발견할 시, 두수의 위치를 교환하고, start 인덱스는 +1 end 인덱스는 -1을 하고, 

 

start index와 end index가 만날때 까지 교환을 수행하고, 루프가 끝난 뒤 start index의 위치를 기준으로 공간을 분리하여 또 위와같은 루프를 반복하면 최종적으로 정렬된 배열이 나오게 된다.

 

 

 

 

[5] 3 8 (9) 2 4 {7} 

 

 ( [ ] = 시작인덱스 ( ) = 기준값 { } = 끝 인덱스 )

 

시작 인덱스 5, 기준값 9 끝 인덱스 7 인 배열이 있을 때

---

5 3 8 [(9)] 2 4 {7} 

 

 

시작 인덱스는 기준값과 값이 같은 9에서 멈춤, 끝 인덱스는 기준값보다 작은 7에서 멈춤, 두 수를 교환

 

기준 값은 7로 바뀔 것이다.

 

---

5 3 8 (7) 2 {4} [9] 

 

시작 인덱스는 7보다 그거나 같은 값을 발견하지 못해 결국 9까지 왔고, 끝 인덱스는 7보다 작은 4를 발견했지만, 이미 시작 인덱스와 끝 인덱스가 만나 교차한 뒤 발견했으므로 교환을 수행하지 않음

 

시작 인덱스의 위치를 기준으로 공간을 분리한다.

 

---

[5] 3 (8) 7 2 {4}   ||    9

 

9는 값이 1개이므로 정렬을 수행할 필요가 없다.

 

---

5 3 [(8)] 7 2 {4}  ||   9

 

위 경우도 기준값 8보다 크거나 같은 값을 발견하지 못해 시작 인덱스가 8까지 도달했고 끝인덱스는 4가 기준값 8보다 작으므로 4를 가리키고 있다. 두 위치를 교환한다.

 

---

5 3 (4) [7] {2} 8   ||   9

 

시작 인덱스는 기준값 4보다 큰 7을 발견했고, 끝 인덱스는 기준값 4보다 작은 2를 발견했다. 또한 두 인덱스가 만나기 이전이므로 교환을 수행한다.

 

---

5 3 (4) {2} [7]  8   ||   9

 

두번째 루프가 지난뒤에는 위와 같은 형태가 되고, 시작 인덱스의 위치인 7을 기준으로 공간을 또 분리한다.

 

---

[5] (3) 4 {2}   ||    [(7)] {8}    ||   9

 

위와 같은 경우도, 지금까지 사용했던 루프 메커니즘을 적용하면

 

첫번째 공간의 경우 기준값 3보다 큰 5와 기준값 3보다 작은 2를 교환하고 나면, 시작인덱스와 끝 인덱스는 3으로 모이게 된다.

 

두번째 공간의 경우 역시, 기준값 7로 시작인덱스와 끝 인덱스가 모이게 된다.

 

 

 

---

2 {[(3)]} 4 5   ||   {[(7)]} 8   ||   9

 

최종 결과는 위와 같을 것이고, 정렬이 되어있음을 확인할 수 있다.

 

랜덤한 배열로, 한번 단계별로 그려보면 이해가 쉬울 것이다.

 

 

자바 [JAVA] - 퀵 정렬 (Quick Sort)

자세한 원리는 위 블로그를 참고하면 좋다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        int N = Integer.valueOf(input1[0]);
        int index = Integer.valueOf(input1[1]);


        int[] arr = new int[N];
        String[] input2 = br.readLine().split(" ");
        for (int i = 0; i < input2.length; i++) {
            arr[i] = Integer.valueOf(input2[i]);
        }
        quickSort(arr);
//        System.out.println(Arrays.toString(arr));
        System.out.println(arr[index-1]);

    }

    private static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int start, int end) {
        int eachPivotPoint = getAfterSwapPivotPoint(array, start, end);
        if (start < eachPivotPoint - 1) {
            quickSort(array, start, eachPivotPoint - 1);
        }
        if (end > eachPivotPoint) {
            quickSort(array, eachPivotPoint, end);
        }
    }

    private static int getAfterSwapPivotPoint(int[] array, int start, int end) {
        int Pivot = array[(start + end) / 2];
        while (start <= end) {
            while (array[start] < Pivot) {
                start++;
            }
            while (array[end] > Pivot) {
                end--;
            }
            if (start <= end) {
                swap(array, start, end);
                start ++;
                end--;
            }
        }
        return start;
    }

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