[코딩테스트] 백준 11004 자바

백준 11004

백준 11004 문제

해당 문제는 n의 최대값이 5,000,000으로 시간 복잡도 O(n2)을 갖는 버블 정렬, 선택 정렬, 삽입 정렬을 사용하면 시간 초과가 된다.

따라서 이 문제는 시간 복잡도 O(n log n)을 갖는 퀵 정렬을 사용하겠다. 그리고 k번째의 수를 알면 되기 때문에 k번째를 수만 알아낸다면 굳이 정렬을 계속할 필요가 없기 때문에 시간 복잡도를 더 줄일 수 있다.

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

public class Boj11004 {

    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()); // k번째 수
        int[] arr = new int[n]; // 숫자 데이터 저장 배열

        st = new StringTokenizer(br.readLine());
        // arr 배열 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(arr, 0, n - 1, k - 1); // quick sort 실행

        System.out.println(arr[k - 1]); // k번째 데이터 출력
    }

    private static void quickSort(int[] arr, int start, int end, int k) {
        if (start < end) {
            int pivot = partition(arr, start, end); // 피벗 구하기

            if (pivot == k) { // k번째 수가 pivot이면 더이상 구할 필요 없음
                return;
            } else if (pivot > k) { // k가 피벗보다 작으면 왼쪽 그룹만 정렬 수행
                quickSort(arr, start, pivot - 1, k);
            } else { // k가 피벗보다 크면 오른쪽 그룹만 정렬 수행
                quickSort(arr, pivot + 1, end, k);
            }
        }
    }

    private static int partition(int[] arr, int start, int end) {
        // 데이터가 두 개인 경우 두 데이터를 정렬
        if (start + 1 == end) {
            if (arr[start] > arr[end]) {
                swap(arr, start, end);
                return end;
            }
        }

        int m = (start + end) / 2; // 중앙값
        swap(arr, start, m); // 중앙값을 1번째 요소로 이동

        int pivot = arr[start]; // start 위치 값을 pivot으로 저장
        int i = start + 1; // 시작점
        int j = end; // 종료점

        while (i <= j) { // 시작점이 종료점보다 작거나 같을 때까지 반복
            while (j >= start && arr[j] > pivot) { // 피벗보다 작은 수가 나올 때까지 j--
                j--;
            }
            while (i <= end && arr[i] < pivot) { // 피벗보다 큰 수가 나올 때까지 i++
                i++;
            }
            if (i <= j) {
                swap(arr, i++, j--); // 피벗보다 큰 수 i++와 피벗보다 작은 수 j--를 swap
            }
        }

        arr[start] = arr[j]; // 경계 index값을 시작 위치에 저장
        arr[j] = pivot; // 피벗 데이터를 나눠진 두 그룹의 경계 index에 저장하기
        return j; // 경계 index 리턴
    }

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

풀이

1. quickSort() 메서드는 partition() 메서드로 구한 pivot이 k번째 인지 확인하고, k가 pivot보다 작으면 왼쪽 그룹만 quickSort() 메서드를 재귀 호출하여 퀵 정렬을 수행하고, k가 pivot보다 크면 오른쪽 그룹만 quickSort() 메서드를 재귀 호출하여 퀵 정렬을 수행한다.
2. partition() 메서드는 데이터가 두 개인 경우에는 두 개의 데이터만 정렬한 후에 pivot값을 반환한다.
3. 데이터가 두 개 이상일 경우에는 중앙값을 구한 다음에 중앙값과 시작 위치의 값을 swap() 해준다.
   • 시작 위치를 pivot값으로 저장하고, pivot 다음 값을 시작점 i로 end 위치를 종료점 j로 저장한다.
   • 반복문을 통해 pivot보다 작은 값이 나올 때까지 j--를 해주고, pivot보다 큰 값이 나올 때까지 i++를 해준다.
   • pivot보다 큰 수 i++와 pivot보다 작은 수 j--를 swap() 해준다.
4. 경계 index값을 시작 위치에 저장한다.
5. pivot 데이터를 나눠진 두 그룹의 경계 index에 저장한다.
6. 경계 index j를 반환한다.