[Java] 백준 11004 K번째 수

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

11004번: K번째 수

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		
		int N = s.nextInt();
		int K = s.nextInt();
		int arr[]= new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = s.nextInt();
		}
		
		Arrays.sort(arr); //시간 초과
        
		/* 버블 정렬 -> 시간 초과
		for(int i=0;i<N;i++) {
			for(int j=1;j<N;j++) {
				if(arr[j-1]>arr[j]) {
					int temp = arr[j-1];
					arr[j-1]=arr[j];
					arr[j]=temp;
				}
			}
		}
		 */
		System.out.print(arr[K-1]);
	}
}

시간 복잡도 상관없이 무조건 정렬만 생각하고 버블 정렬로 풀었더니 시간 초과가 나왔다. Arrays.sort()를 써도 시간 초과가 나온다. 여기서 버블 정렬이란 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 

구현이 간단한 장점에 비해 교환 횟수가 많아 시간 복잡도는 T(n) = O(n^2)으로 잘 쓰이지 않는다고 한다.

 

따라서 이 문제는 퀵 정렬로 풀어야 한다.

퀵 정렬은 분할(partition)을 통해 pivot을 기준으로 왼쪽과 오른쪽의 부분집합을 각각 정렬하는 방법이다.

퀵 정렬은 시간 복잡도가 O(nlog₂n)로 가장 빠르고 공간 복잡도는O(log n)다.

 

quick sort로 구현

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
		
		int N = s.nextInt();
		int K = s.nextInt();
		int arr[]= new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = s.nextInt();
		}
		
		quicksort(arr,0,N-1);
		
		System.out.print(arr[K-1]);
	

	}
	
	public static void quicksort(int[] arr,int left,int right) {
		int l=left;
		int r= right; 
		int pivot = (l+right)/2;
		
		while(l<r) {
			while(arr[pivot]>arr[l]) l++;
			while(arr[pivot]<arr[r]) r--;
			
			if(l<=r) {
				int temp=arr[r];
				arr[r]=arr[l];
				arr[l]=temp;
				l++;
				r--;
			}
		}
		
		if(left<r) quicksort(arr,left,r);
		if(l<right) quicksort(arr,l,right);

	}
}

 

그런데 퀵 정렬로 구현해봐도 계속 '틀렸습니다'가 나온다. 뭐가 문젠지 모르겠다. Help me,,