[JAVA][Baekjoon] 11004번 K번째 수 🌟🌟🌟

https://www.acmicpc.net/problem/11004

---

📌 접근 방식

N의 최대값이 5백만이기 때문에 단순히 Arrays.sort() 같은 걸로 풀면 시간 초과가 날 확률이 높아요.
그래서 퀵 정렬을 사용해 풀어보았습니다.

[알고리즘] 퀵 정렬(Quick Sort)이란?

---

✅ PASS CODE

import java.io.*;
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 [] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr, 0, N-1, K-1);
        System.out.println(arr[K-1]); // K번째 값 출력
    }

    public static void quickSort(int[] arr, int S, int E, int K) {
        if(S < E) {
            int pivot = partition(arr, S, E);
            if(pivot == K) {
                return; // K번째 값 찾으면 바로 종료
            } else if (pivot < K) {
                quickSort(arr, pivot + 1, E, K); // 오른쪽 부분 탐색
            } else {
                quickSort(arr, S, pivot - 1, K); // 왼쪽 부분 탐색
            }
        }
    }

    public static int partition(int [] arr, int S, int E) {
        if(S+1 == E) {
            if(arr[S] > arr[E]) {
                swap(arr, S, E);
            }
            return E;
        }
        int M = (S + E) / 2;
        swap(arr, S, M); // 중앙값을 피벗으로 설정
        int pivot = arr[S];
        int i = S + 1;
        int j = E;

        while(i <= j) {
            while(j >= S+1 && arr[j] > pivot) j--; // 오른쪽에서 피벗보다 작은 값 찾기
            while(i <= E && arr[i] < pivot) i++; // 왼쪽에서 피벗보다 큰 값 찾기
            if(i <= j) swap(arr, i++, j--); // 서로 교환
        }
        arr[S] = arr[j];
        arr[j] = pivot; // 피벗 위치 확정
        return j; // 피벗 위치 반환
    }

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

📌 코드 분석

1. 메인 함수
   • 입력을 받고, 배열에 저장한 뒤, 퀵 정렬을 호출합니다.
   • K번째 값을 출력합니다. (배열 인덱스는 0부터 시작하니까 K−1K-1K−1로 접근)
2. quickSort 함수
   
   • 피벗 위치를 기준으로 K가 피벗보다 앞에 있는지, 뒤에 있는지 확인하며 정렬 범위를 줄여 나갑니다.
   • K와 피벗 위치가 같다면 정렬을 멈춥니다.
3. partition 함수
   • 피벗을 기준으로 작은 값과 큰 값을 분리합니다.
   • 중앙값을 피벗으로 설정하고, 배열을 스왑하면서 정렬합니다.
4. swap 함수
   • 배열의 두 값을 간단히 교환합니다.

---

반응형

📌 느낀 점

이번 문제는 자칫 Arrays.sort() 같은 쉬운 방법으로 접근하면 큰 입력값에서 시간이 너무 오래 걸릴 수 있습니다.

퀵 정렬을 활용하면서, 정렬 알고리즘의 원리를 다시 한번 이해하게 된 것 같아요.

그리고 중간중간 디버깅하면서 실수를 잡아내는 과정도 재미있었습니다. 특히 partition에서 조건문 잘못 써서 고생 좀 했어요. 😅