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

dev-jjun·2023년 1월 10일

boj 알고리즘

코딩테스트 준비

목록 보기

6/11

🔗 문제

BOJ 11004 : K번째 수

난이도 - 실버 5

알고리즘 분류 - 정렬

💬 풀이

Java는 C++, Python에 비해서 알고리즘 대회나 문제 풀이에 주력 언어로 사용되는 경우가 비교적 적다. 그 이유는 Java의 개념이 객체지향 등에 의해 문법에서 비교적 어렵고 속도가 느리기 때문에 알고리즘 특화 언어로 사용되는 경우가 적다.
하지만 나는 Java로 알고리즘을 공부하는 만큼 시간초과에 의한 실패를 더 많이 경험할 확률이 높으므로 어떻게 하면 시간초과 문제를 최소화할 수 있을지 고민하고 글로 정리해보았다.

또한, 정렬에서 가장 빠른 알고리즘인 퀵 정렬을 이용해 문제를 풀이하였다.

퀵 정렬 (Quick Sort)

퀵 정렬은 피벗을 기준으로 리스트를 크기가 다를 수 있는 두 배열로 나누어가며 크기가 1인 리스트가 될 때까지 분할한 후에 정복하는 방식이다. 요소의 개수가 1이 될 때까지 쪼개가며 정렬을 하기 때문에 시간 복잡도는 O( $n*log n$ ), 최대 O( $n^2$ ) 를 가지며 가장 빠른 정렬 알고리즘으로 꼽힌다.

문제는 quickSort() 메서드 정의 후 재귀적인 방식으로 풀이했는데, 해당 호출에서의 left와 right, pivot값을 구해야 하므로 pl과 pr 변수를 두고 이들을 새로운 left와 right 값이 되도록 하였다. 피벗을 하나 잡고 이를 기준으로 왼쪽에서는 피벗보다 작은 값, 오른쪽에서는 피벗보다 큰 값을 찾은 뒤에 두 원소를 swap 한다. 이때 왼쪽과 오른쪽에서의 탐색 위치가 엇갈리지 않게 하기 위하여 while 문을 돌며 pl과 pr값을 조정해주고 left와 right의 값과 각각 비교하여 정렬이 끝날 때까지 재귀 호출을 진행하여 위 과정을 반복하게 된다.

💻 코드

package Baekjoon;

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

public class _11004 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] nums = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i=0; i<nums.length; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        // 퀵 정렬을 이용하여 정수배열 정렬
        quickSort(nums, 0, N-1);

        bw.write(String.valueOf(nums[K-1]));   // BufferedWriter 를 사용하려면 String 형으로 변환이 필요하다.
        bw.flush();

        br.close();
        bw.close();
    }

    public static void quickSort(int[] arr, int left, int right) {

        // 재귀 방식으로 양끝의 인덱스를 변화시킬 것이므로, 현재 상태에서의 검사할 끝단 인덱스 저장
        int pl = left;
        int pr = right;
        int x = arr[(pl+pr) / 2];

        do {
            while (arr[pl] < x) pl++;
            while (arr[pr] > x) pr--;

            if (pl <= pr)
                swap(arr, pl++, pr--);
        } while (pl <= pr);

        // left와 right 의 대소관계가 유지될 시에만 퀵 정렬 함수 재귀호출
        if (left < pr) quickSort(arr, left, pr);
        if (pl > right) quickSort(arr, pl, right);
    }

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