[PS] 백준 11004번 K번째 수

문제

11004번: K번째 수

 

풀이

퀵소트 참고글
참고한 풀이1
참고한 풀이2

 

Quick Sort
퀵소트는 partition 메서드를 중심으로 재귀호출하는 방식으로 구현된다.

• pivot의 자리가 선택(partition 메서드 한 번 실행)된 후 부분집합으로 계속 쪼개져 정렬하는 분할 정복 방식 정렬 알고리즘
• pivot을 기준으로 작은 수들은 pivot의 왼쪽, 큰 수들은 오른쪽에 배치
• 이 과정을 재귀적으로 반복하면 모든 수가 정렬이 된다
• pivot을 선택하는 방법에 따라 처리속도가 달라진다
  • 첫번째 요소 / 중간 요소 / 마지막 요소 / 랜덤 선택
• 첫번째 요소를 선택하는 방식을 통해 전체적인 진행
• pivot을 선택하고 left, right가 pivot을 향한 방향으로 탐색하다 pivot보다 작은 수, 큰 수를 찾은 후 두 값을 교환한다.

public int partition(int[] array, int left, int right) {
    int pivot = array[left];
    int i = left, j = right;

    while (i < j){
        while (pivot < array[j]) {
            j--; //← 피벗보다 작은 수를 찾는다.
        }

        while (i < j && pivot >= array[i]) {
            i++; //→ 피벗보다 큰 수를 찾는다.
        }
        swap(array, i, j); //i, j 교환
    }
    //i, j교차하면 현재 피벗과 교환
    array[left] = array[i];
    array[i] = pivot;

    return i; //(변경된 위치의)피벗 위치 리턴
}

분할된 왼쪽 영역과 오른쪽 영역은 각 분할된 영역에서 다시 partition() 과정을 진행

public void quicksort(int[] array, int left, int right){
    if (left >= right) return;
    int pi = partition();

    quicksort(array, left, pi - 1);
    quicksort(array, pi + 1, right);
}

• 요소들이 역순으로 존재했을 때 : 최악의 경우 시간복잡도가 O(n^2)
• pivot을 중간 요소로 선택한다면, 이 문제를 해결
• 먼 거리 교환 처리와 캐시 효율(한번 선택된 기준은 제외한다) 등의 이유로 O(nlogn) 의 시간복잡도를 가지는 다른 소트보다 빠르다

 

Quick Selection

• N개의 수에서 K번 째 수를 반환하는 경우에 사용되는 특정한 알고리즘
• Quick sort의 과정으로 결정된 pivot의 자리값과 입력받은 k값을 비교해 해당하는 부분만 계속해서 분할 정복
• 즉 pivot값이 문제에서 요구하는 k번째 값이라면 바로 메소드를 끝낸다.

아니 근데 참고한 블로그 글의 코드 복붙해서 돌려봐도 시간초과 뜨네. 어쩌란거야. 자야겠다 ㅠㅠㅜ

 

코드

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

public class Main {
    static int K;

    public static void main(String[] args) throws NumberFormatException, IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int[] A = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(quickSearch(A,0,N-1));

    }

    public static int quickSearch(int[] arr, int left, int right) {
        int pi = partition(arr,left,right);

        //K번째 수 = arr[K-1]
        if(pi == K-1) return arr[pi];
        else if(K-1 < pi) return quickSearch(arr,left,pi-1); // ( 여기를 찾자 )K( pi )
        else return quickSearch(arr,pi+1,right);
    }

    public static int partition(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        swap(arr,left,mid); //첫번째 요소와 중간 요소를 교환(중간요소를 피벗으로 선택)
        
        int pivot = arr[left]; //피벗 선택
        int i = left, j = right;

        while(i < j) {
            while(pivot <arr[j]) { //피벗보다 작은 수 찾을때까지
                j--;
            }

            while(i < j && pivot >= arr[i]) { //피벗보다 큰 수 찾을때까지
                i++;
            }
            swap(arr,i,j); //i, j 교환
        }
        //i와 j가 교차하면 pivot과 교환
        swap(arr, i, left);

        return i; //교환된 피벗 위치 리턴
    }

    public static void swap(int[] arr, int i, int j) {
        int temp =arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}