1. 문제 설명 📌

2. 접근 방식 🗃️

KEY WORD: QUICK SORTING

사실 JAVA 내부 라이브러리에 있는 Sorting을 쓰면 간단히 해결되는 문제이지만, Qucik Sorting 연습을 위해 Quick Sorting을 사용해 보았다. quick sorting의 경우, 최악의 시간 복잡도가 O( $N^2$ )이라서 문제에 제시된 최대 데이터 량을 보면, 시간초과가 나야 하는 것이 맞다. (아마 Quick Sorting을 쓰면 시간 초과가 나는 테스트 케이스를 안 넣어놓은 것 같다.)

(1) 큰 흐름

(1) 현재 정렬해야 하는 영역의 중앙값을 PIVOT으로 선정
(2) PIVOT을 영역 최좌단 값과 자리 교체. (pivot은 비교 대상에 속하지 않도록 하기 위함.)
(3) PIVOT을 제외한 전 영역에 대하여 정렬 진행 (마주보는 투 포인터 활용)
- (3-1) L 포인터는 왼쪽에서 출발, R 포인터는 오른쪽에서 출발
- (3-2) L 포인터는 pivot보다 작은 값을 만나면 계속 전진 (크거나 같은 값을 만나면 STOP)
- (3-3) R 포인터는 반대로 pivot보다 큰 값을 만나면 전진 (반대의 경우 STOP)
- (3-4) L 과 R이 둘 다 멈춰있을 때, 자리 교체 (pivot보다 작은 값은 오른쪽에, 큰 값은 왼쪽에 몰기 위함.)

3. 코드 소개 🔎

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


public class Main {

    static int [] arr;

    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());
        arr = new int [N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quick_sort(0, N-1);
        System.out.println(arr[K-1]);
    }

    private static void quick_sort (int start, int end) {
       // 0. 기저 조건
        if(end - start == 1){
            swap(start, end);
        }
        if(start >= end) return;
        // 1. 본계산
        int pivot = start + (end - start)/2;
        int pivot_value = arr[pivot];
        swap(pivot, start);                 // pivot 한 쪽으로 몰아서 계산에 영향 안 주기
        int L = start+1; int R = end;
        while (L <= R) {
            while (L <= end && arr[L] < pivot_value) L++;
            while (R >= 0 && arr[R] > pivot_value) R--;
            if(L <= R) {
                swap(L,R);
                L++; R--;
            }
        }
        swap(start, R);
        quick_sort(start, R-1);
        quick_sort(L, end);
    }

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

4. 배운 것들 🎯

(1) 처음에 구현한 실패 코드

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


public class Main {

    static int [] arr;

    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());
        arr = new int [N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quick_sort(0, N-1);
        System.out.println(arr[K-1]);
    }

    private static void quick_sort (int start, int end) {
        // 0. 기저 조건
        if(start >= end) return;

        int pivot = start + (end - start)/2;
        int pivot_value = arr[pivot];
        int L = start; int R = end;
        while (L <= R){
            while (arr[L] <= pivot_value) L++;                     // a
            while (arr[R] > pivot_value) R--;
            if(arr[L] > pivot_value && arr[R] <= pivot_value){    // b
                int tmp = arr[L];
                arr[L] = arr[R];
                arr[R] = tmp;
                L++; R--;
            }
        }
        quick_sort(start, R);
        quick_sort(L, end);
    }
}

안되었던 이유 설명!

주석 a 부분을 보면, L 포인터가 가리키는 값이 Pivot_value와 같은 경우에도 전진하였다. 이렇게 하면, 값이 SWAP 되어야 하는데, 되지 않고 무한 LOOP를 도는 경우가 생긴다. 예를 들어 [4,1,2,3,5]라는 예시를 생각해보자.

첫 정렬은 범위가 전체이고 PIVOT은 2이다. SWAP은 4와 2의 자리교체 한 번 일어난다.

두 번째 정렬은 범위가 arr[0] ~ arr[1] 이고 PIVOT은 2이다. 이 경우에 [2,1]에 대해서 진행하는데, 우리가 바라는 것은 둘의 자리교체이다. 하지만 위와 같이 코드를 짜면, L포인터가 자꾸 2를 지나쳐서 정렬은 되지 않고, 다음 재귀에도 같은 영역, 같은 Pivot에 대해서 진행하게 되어 무한 루프를 돌게 된다. 따라서 현재 포인터가 가리키는 값이 PIVOT과 같아도 멈춰야 한다.

주석 b의 경우 조건문 내용이 사실상 위에 적힌 While문 두 개와 같아서 의미가 없다. 진짜 적었어야 하는 내용은 L <= R을 만족하냐 이다. 우리는 L과 R이 엇갈리면 즉시 반복문을 종료하길 바란다. 왜냐하면 그래야지 잘못된 계산이 되지 않을 것이기 때문이다.

L과 R이 엇갈리면, L은 pivot보다 크거나 같은 값들을 만날 것이고, R은 무조건 Pivot보다 작거나 같은 값을 만날 것이다. 이렇게 되면 필요 없는 SWAP이 일어나 계산을 망치게 된다.

(2) 실패 코드 보완

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


public class Main {

    static int [] arr;

    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());
        arr = new int [N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quick_sort(0, N-1);
        System.out.println(arr[K-1]);
    }

    private static void quick_sort (int start, int end) {
        // 0. 기저 조건
        if(start >= end) return;

        int pivot = start + (end - start)/2;
        int pivot_value = arr[pivot];
        int L = start; int R = end;
        while (L <= R){
            while (arr[L] < pivot_value) L++;    // 바뀐 부분 - Pivot과 값이 같으면 움직이지 않기
            while (arr[R] > pivot_value) R--;
            if(L <= R){                         // 바뀐 부분 - 그냥 L <=R이면 SWAP
                int tmp = arr[L];
                arr[L] = arr[R];
                arr[R] = tmp;
                L++; R--;
            }
        }
        quick_sort(start, R);
        quick_sort(L, end);
    }
}

(3) 모범 답안과 (2)번 코드의 효율성 비교

(2)번 코드의 경우에 PIVOT을 정렬 대상에 매번 포함 시키고 있다. 이러면 PIVOT의 자리 찾기를 위한 불 필요한 연산이 매 연산마다 더 들어간다는 것이다. PIVOT은 정렬의 기준이기에, 정렬이 끝나고, 그 둘의 접점 사이에만 넣어주면 된다.

이러한 (2)번 코드의 단점을 보완한 것이 정답 코드이다. 어떻게 보안 했는지 살펴보면 다음과 같다.