[백준 11004] K번째 수 (JAVA)

백준 11004번 문제  - K번째 수

11004번: K번째 수

---

 

문제 분석

 

 

 

수를 오름차순으로 정렬하고, k번째 수를 알아내는 문제

 

---

해결 키 포인트

 

• 배열을 정렬
  • Arrays.sort
  • 퀵정렬..?
• 정렬 후 k번째 수 출력 (k번째 수의 index는 k-1)

 

---

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N과 K 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 숫자 A 배열 입력
        st = new StringTokenizer(br.readLine());

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

        // 수 정렬
        Arrays.sort(nums);
        
        System.out.println(nums[K - 1]);
    }
}

 

 

---

퀵 정렬로 코딩

 

퀵 정렬로 정렬한 후 k번째 수를 얻어내고자 했는데, 실패했다.. 

 

퀵 정렬로 코딩한 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N과 K 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 숫자 A 배열 입력
        st = new StringTokenizer(br.readLine());

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

        // 퀵 정렬로 k 전 수까지 정렬
        quickSort(nums, 0, nums.length - 1, K);

        System.out.println(nums[K - 1]);
    }


    public static void quickSort(int[] arr, int start, int end, int k) {

        if (start < end) {
            int pivot = partition(arr, start, end);
            if (pivot == k)
                return;
                // pibot이 k보다 클 경우, pibot 앞 배열 중 k값이 존재하는 것이므로 앞만 sort
            else if (pivot > k) {
                quickSort(arr, start, pivot - 1, k);
            }
            // pibot이 k보다 작을 경우, pibot 뒤 배열 중 k값이 존재하는 것이므로 뒤만 sort
            else {
                quickSort(arr, pivot + 1, end, k);
            }
        }
    }

    private static int partition(int[] arr, int start, int end) {
        // 중앙 값을 pibot으로
        int mid = (start + end) / 2;
        swap(arr, start, mid);
        int pivot = arr[start];
        int s=start, e=end;

        while(s < e) {
            // 피벗보다 작은 수 나올 때까지
            while(pivot < arr[e]) {
                e--;
            }
            // 피벗보다 큰 수 나올 때까지
            while(s < e && pivot >= arr[s]) {
                s++;
            }

            // s, e 교체
            swap(arr, s, e);
        }
        arr[start] = arr[s];
        arr[s] = pivot;
        return s;
    }

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

 

퀵 정렬 설명

 

Pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심

 

Do it! 알고리즘 코딩 테스트 기본