[JAVA/백준] 11004번 : K번째 수

[문제]

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.


<Input>
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

<Output>
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

<examples>
-입력

5
5
4
3
2
1

-출력

1
2
3
4
5

 

[풀이]

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

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());
        st = new StringTokenizer(br.readLine());
        int A[] = new int[N];
        for (int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(A,0,N-1,K-1);
        System.out.println(A[K-1]);
    }

    public static void quickSort(int[] a, int S, int E, int K) {
        //S부터E까지 가진 배열 a[]의 K번째 수 구하기
        if(S<E){
            int pivot = partition(a,S,E);
            if (pivot==K) //K가 피벗이면 더이상 구할 필요 없음
                return;
            else if (K<pivot) { //K가 피벗보다 작으면 왼쪽 그룹만 정렬 수행하기
                quickSort(a,S,pivot-1,K);
            }
            else //K가 피벗보다 크면 오른쪽 그룹만 정렬 수행하기
                quickSort(a,pivot+1,E,K);
        }
    }

    public static int partition(int[] a, int s, int e) {
        int M = (s+e)/2;
        swap(a,s,M);
        int pivot = a[s];
        int i = s, j = e;
        while (i<j){
            while (pivot < a[j]){
                j--;
            }
            while (i<j && pivot >= a[i]){
                i++;
            }
            swap(a,i,j); //그러다 s(=i)와 e(=j)가 만나면 스왑
        }
        a[s] = a[i];
        a[i] = pivot;
        return i;
    }

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

 

 

---

 

O(nlogn)의 시간 복잡도를 가진 퀵 정렬을 이용해 풀 수 있는 문제이다.

중앙값으로 설정할 피벗을 구하고 i,j 포인터를 각 끝으로 두어 

j>pivot 이면 => j--

그게 아니라면 i와 pivot을 비교하기 시작

i<pivot && i<j 이면 => i++

이러면 i와 j가 만나는 지점이 온다.

그럼 그 위치의 값을 피벗의 값과 swap!

 

퀵 정렬 이용한 문제인데

사실 쫌 어렵다..