11004번 문제 링크

위 문제는 자바에서 제공하는 Arrays 에 sort가 아닌 O(nlogn) 시간 복잡도를 가지는 퀵정렬을 통해 풀어보려고 합니다.

개념 자체는 어렵지는 않지만, 막상 구현하련니깐 많이 헤깔리고 놓쳤던 부분들이 많았던 문제였습니다.

하루 아침에 코드가 뽝 늘면 좋겠지만.. 그렇지는 않으니깐! 차근차근 처음볼 때 확실하게 봐둬야 겠다는 생각으로 포스팅하였습니다.

퀵정렬의 핵심 이론은 pivot 이라는 기준값을 선정하여 투 포인터로 가리키는 끝 요소들의 크기를 비교하여 정렬한다는 점입니다.

과정을 천천히 설명하면 다음과 같습니다.

핵심 과정
1. pivot을 설정
2. 아래 분할 과정을 거쳐 pivot을 기준으로 두 집합으로 분할.
3. 분할한 집합에서 각각 pivot을 선정.
4. 분할한 집합이 1개 이하가 될때까지 위 과정을 반복.

분할 과정

1. pivot이 가리키는 값과 start가 가리키는 값을 비교하여 start가 pivot 보다 작으면, start 포인터가 오른쪽으로 한칸 이동한다.

2. pivot이 가리키는 값과 end가 가리키는 값을 비교하여 end가 pivot 보다 크면, end 포인터가 왼쪽으로 한칸 이동한다.

3. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end 가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.

4. start와 end가 만날때까지 위 과정을 반복한다.

5. start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

😀 성공

import java.io.*;
import java.util.*;

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());
        }
        
        // 퀵정렬
        quickSort(arr, 0, N-1, K-1);
        
        // 출력
        System.out.println(arr[K-1]);
    }
    
    // 퀵정렬 함수
    static void quickSort(int[] arr, int S, int E, int K){
        if(S < E){
            int pivot = partition(arr,S,E);
            if(pivot == K){
                return;
            }
            else if(pivot > K){
                quickSort(arr,S,pivot-1,K);
            }
            else{
                quickSort(arr,pivot+1, E, K);
            }
        }
    }
    
    // pivot 기준 수열 분할 함수
    static int partition(int[] arr, int S, int E){
        if(S+1 == E){
            if(arr[S] > arr[E]) swap(arr,S,E);
            return E;
        }
        int M = (S+E)/2;
        swap(arr,S,M);
        int pivot = arr[S];
        int  i =S+1, j=E;
        while(i <= j){
            while(j >= S +1 && arr[j] > pivot){
                j--;
            }
            
            while(i <= E && arr[i] < pivot){
                i++;
            }
            
            if(i <= j){
                swap(arr,i++,j--);
            }
        }
        
        arr[S] = arr[j];
        arr[j] = pivot;
        return j;
    }
    
    // 위치 변환 함수
    static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}