[백준] 정렬 - 11004번, k번째 수 (quicksort로 풀 수 있을까?)

문) 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입) 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출) A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

---

풀이 & 코드

솔직히 푼 거 후회했다. 7전 1승의 너덜너덜한 승리를 쥐고, 연구과제로 남기려고 작성한다.

 

1. 라이브러리 활용

1차 시도 : 시간 초과 ❌

제한 시간 2초, 찾아보니 자바는 (제한시간)*2 +1 초 준다고 한다. 그런데도 초과.

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

public class Main{
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        bw.write(String.valueOf(arr[k-1]));

        sc.close();
        bw.flush();
        bw.close();
    }
}

입력받을 때 시간 소모가 많은 탓이라고 생각했다(Scanner).

다른 이유도 있을까하여 질문 게시글을 찾다보니, 세상에 <Quick Sort> 얘기가 나오는 것이다.

 

알고리즘 시간 때 배운 정렬을 왜 안 써먹었지 충격에 남은 도전은 QuickSort 에 전념하게 된다.

(여기에 너무 집착하였던 게 패인의 요인이었다.)

 

 

2. Quick Sort

Quick Sort 복습

pivot, low, high가 있고, pivot 다음 부터 low가 할당되고 n값 있는 쪽이 high 다.

주요 개념에는 Swap과 Cross가 있다.

 

low와 high가 멈추면(stop), 두 수의 교환이 일어난다(Swap).

• low : pivot보다 더 큰 값을 만나면 stop
• high : pivot보다 더 작은 값을 만나면 stop
• low는 오른쪽으로, high는 왼쪽으로 이동하며 같이 진행한다.

high <= low 되면 pivot값과 바뀐다(Cross).

 

흑, 슬프게도 개념은 이해가 되었으나 코드로 작성하려니 까마득해졌다.

여러 블로그를 탐방하며 코드를 작성했다.

 

제출 코드

2~6차 시도 : 시간 초과 또는 틀렸습니다. ❌

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

public class Main{
    public static int partition(Integer[] arr, int left, int right) {
        int mid = (left + right) / 2;
        swap(arr, left, mid); //중앙값을 첫 번째 요소(pivot)으로 이동
        int pivot = arr[left];
        int i = left, j = right;
        while(i<j) {
            //j는 오른쪽에서 왼쪽으로, pivot보다 작은 수 찾음(Stop).
            while(pivot < arr[j]) {
                j--;
            }
            //i는 왼쪽에서 오른쪽으로, pivot보다 큰 수 찾음(Stop).
            while(i<j && pivot >= arr[i]) {
                i++;
            }
            swap(arr, i, j); //찾은 i와 j를 교환
        }
        //arr[i]=arr[j]가 되었을 때 반복문에서 벗어나게 됨(Cross).
        //Cross : Pivot과 교환
        arr[left] = arr[i];
        arr[i] = pivot;
        return i;
    }
    public static void swap(Integer[] arr, int a, int b) {
        int temp = arr[b];
        arr[b] = arr[a];
        arr[a] = temp;
    }
    public static void quicksort(Integer[] arr, int left, int right, int k) {
        if(left < right) {
            //partition을 통해 구한 pivot과 k를 비교해 해당 부분집합에 재귀호출을 반복
            int pivot = partition(arr, left, right);
            if (pivot == k-1) return;
            else if (pivot > k-1) quicksort(arr, left, pivot - 1, k);
            else quicksort(arr, pivot + 1, right, k);
        }
    }

    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());
        Integer[] arr = new Integer[n];

        st = new StringTokenizer(br.readLine());
        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]);

        br.close();
    }
}

더할나위 없이 좋은 코드라고 생각했다.

그런데 결과는 <시간 초과, 틀렸습니다.> 제시된 예제와 질문 게시판의 반례와

이 문제를 푼 사람들이 블로그에 적어둔 반례도 다 통과했다. 그런데 왜???

 

 

어느 지식인의 FAQ를 보게 되었다. 그렇다. QuickSort로는 풀 수 없고, QuickSelect를 사용해야 한다.

그럼 이전에 통과한 사람들은 뭘까 싶지만,

세월이 흘러... 백준이 업데이트가 되었다고 생각하자... 지금 통과가 안 되는 걸 어떡하나...

 

악으로 깡으로 찾다보니 int[]  배열보다 WrapperClass인 Integer[]로 했을 때 빠르다는 것도 발견했다.

(위의 코드) 제출하니 틀렸댄다. int[]로 하면 시간 초과.

새롭게 quickSelect를 공부해서 이 문제를 정복하는 건... 힘들 것 같아서 일단 기록 먼저 해둔다.

 

3. 최종 제출 코드

그래서 어떤 선택을 했나? 다시 원점으로 돌아갔다^^.

입출력 코드만 바꿔서 제출하니 통과다(메모리, 시간 모두 흐음 싶지만 어쨌든 통과).

7차 시도 : 성공 ✅

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        Integer[] arr = new Integer[n];

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

        Arrays.sort(arr);
        System.out.println(arr[k-1]);
    }
}

---

다 찢겼지만 이겼어요

이 문제는 여러모로 의미가 있었다(하하^^^^).

1. quickSort로 정녕 풀 수 없는 것인가라는 연구 과제로 남기게 되었고

2. 시간 소요를 위해 int[]보다 Integer[]를 쓰는 것이 더 좋을 때가 있다는 것을 알게 되었다.

3. quickSort가 가지는 최악의 시간 복잡도를 고려하여... 적절한 알고리즘을 선택해야 한다는 깨달음도 얻었다.

 

그 밖에 System.currentTimeMills(); 을 적극 활용해서 무의미한 제출을 없애야겠다고 생각했다.

 

 

[참고] QuickSort 작성할 때 도움이 되었던 블로그

https://log-laboratory.tistory.com/45

https://upcurvewave.tistory.com/131

https://velog.io/@chosj1526/%EB%B0%B1%EC%A4%80-11004-K%EB%B2%88%EC%A7%B8-%EC%88%98-JAVA#%EC%A0%9C%EC%B6%9C%EC%BD%94%EB%93%9C