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

🔺 문제

11004번: K번째 수

 

🔺 코드

import java.util.*;
import java.io.*;
 
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[] A = new int[N];
        
        st = new StringTokenizer(br.readLine()," ");
        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) {
        if(S < E) {
            int pivot = partition(A, S, E);
            
            if(pivot == K)     return;
            else if(K < pivot) quickSort(A, S, pivot - 1, K);
            else               quickSort(A, pivot + 1, E, K); 
        }
    }
    
    // 피벗 구하기 메소드
    public static int partition(int[] A, int S, int E) {
        // 데이터가 2개인 경우, 바로 비교해 정렬
        if(S + 1 == E) {
            if(A[S] > A[E]) swap(A, S, E);
            return E;
        }
        
        int M = (S + E) / 2;    // 배열 중간 위치를 pivot으로 설정
        swap(A, S, M);          // 중앙값을 첫 번째 요소로 이동
        
 
        int pivot = A[S];
        int i = S + 1;
        int j = E;
        
        while(i <= j) {
            // 피벗보다 큰 수가 나올 때까지 i++
            while(pivot > A[i]) {
                i++;
            }            
            // 피벗보다 작은 수가 나올 때까지 j--
            while(pivot < A[j]) {
                j--;
            }
            
            // 찾은 i와 j를 swap
            if(i <= j) {
                swap(A, i++, j--);    // 새로운 파티션 범위 지정 위해 i++, j--해주는 것
            }
        }
        
        // 피벗 데이터를 나눠진 두 그룹의 경계 idx에 저장 (i로 해도 상관 x)
        A[S] = A[j];
        A[j] = pivot;
        return j;   // 경계 idx 리턴
    }
    
    public static void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

✅ 해결 아이디어
- 퀵 정렬 이용 (∵ 시간 복잡도 O(nlogn)에서 정렬 수행해야 하므로)
- 퀵 정렬 메소드, 피봇 구하는 함수, swap 함수 구현.

---

🔺 다른 풀이들

- 풀이1)

[백준,BOJ 11004] k번째 수( JAVA 구현)

 

 

- 풀이2)

[JAVA][BOJ][S5] 11004. K번째 수

리스트를 만들고, Collections.sort()를 이용하심.

 

 

 

- 풀이3)

[PS] 백준 11004번 K번째 수

퀵 정렬 사용하신 건 같은데 설명을 잘 해주셔서.. 복습용으로다가 올려놓기..

---

💬 느낀 점

유용한 퀵 정렬.... 평균 시간 복잡도가 O(nlogn)밖에 안 되는,,,,,

암튼,,, 스스로 구현할 수 있을때까지 복습하잣

 

퀵 정렬은 분할 정복의 일종~~

1회독	2회독	3회독	4회독	5회독
V	6/13

 

---

(참고)

[자료구조/Java] 퀵 정렬(Quick Sort)

 

- Do it 알고리즘 코딩테스트 자바편