[퀵 정렬] 백준 11004번

문제

- Array를 오름차순 정렬했을 때 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오
- 데이터 개수 ( 1 <= N <= 5,000,000 )
- K번째 수 ( 1 <= K <= N)

 

문제 분석

시간 제한 2초 : 2억번 연산 내에 구현
(NlogN 일경우, 시간제한에 있어서는 통과할 시간복잡도이다)
- 오름차순 정렬이 필요하므로, 퀵정렬을 이용한 풀이를 진행

• pivot 정하는 방법
  • pivot == k : k 번째 수를 찾은 것이므로 알고리즘을 종료
  • pivot > k : pivot의 왼쪽 부분에 K가 있으므로 왼쪽 (S ~ pivot -1) 만 정렬을 수행한다
  • pivot < k : pivot의 오른쪽 부분에 K가 있으므로 오른쪽(pivot -1 -E)만 정렬을 수행한다
• 퀵정렬은 pivot이 지정되있는 곳이 정렬된 숫자이다 

슈도 코드

N(숫자의 개수) K(K번째 수)
A(숫자 데이터 저장 배열)
for(N만큼 반복하기){
    배열 저장하기
}
퀵소트 실행
K번째 데이터 출력


[별도함수]
퀵소트함수( 시작, 종료, K){
    피벗구하기 함수( 시작, 종료 )
    if ( 피벗 == k ) 종료
    else if (k < 피벗) 퀵소트 실행 (시작, 피벗-1, K)
    else 퀵 소트 수행하기 (피벗 +1 , 종료 ,K)
}

피벗구하기 함수( 시작, 종료 )
{
    중앙값을 피벗으로 설정
    i (시작점), j (종료점)
    while(i < j){
        피벗보다 큰 수가 나올때까지 i++
        피벗보다 작은 수가 나올 때까지 j--
        찾은 i와 j데이터를 swap
    }
    피벗 데이터를 나눠진 두 그룹의 경계 index 에 저장하기
}

 

구현하기

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

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

        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[size];
        for(int i =0; i < size; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr, 0, arr.length - 1, k - 1);
        System.out.println(arr[k - 1]);
    }


    private static void quickSort(int[] arr, int startIndex, int endIndex, int k){
        if (startIndex < endIndex){
            int pivot = partition(arr, startIndex, endIndex);
            if (pivot == k){
                return;
            }else if(k < pivot){
                quickSort(arr, startIndex, pivot - 1, k);
            }else{
                quickSort(arr, pivot + 1, endIndex, k);
            }
        }
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
        int middlePointer = (startIndex+endIndex)/2;
        int pivot = arr[middlePointer];
        swap(arr, startIndex, middlePointer);
        int leftPointer = startIndex + 1;
        int rightPointer = endIndex;

        while( leftPointer <= rightPointer){
            while(leftPointer <= rightPointer && arr[leftPointer] < pivot){
                leftPointer++;
            }
            while(leftPointer  <= rightPointer && arr[rightPointer] > pivot){
                rightPointer--;
            }
            if(leftPointer <= rightPointer){
                swap(arr,leftPointer, rightPointer);
                leftPointer++;
                rightPointer--;
            }
        }

        swap(arr, rightPointer, startIndex);
        return rightPointer;
    }

    private static void swap(int[] arr, int leftIndex, int rightIndex){
        int temp = arr[leftIndex];
        arr[leftIndex] = arr[rightIndex];
        arr[rightIndex] = temp;
    }
}