[백준] 11004. K번째 수 (Java)

 

🔒 문제

11004번: K번째 수

 

🔑 알고리즘

정렬

 

💡  풀이

원소의 개수 N이 최대 5백만이므로 O(N^2)이 아닌 O(NlogN)의 시간 복잡도를 가지는 정렬 방식을 사용해야한다.

Arrays.sort()의 경우 dual pivot quick sort를 사용하여 최악의 경우 O(N^2)의 시간 복잡도를 갖지만

Collections.sort()의 경우 tim sort를 사용하여 최악의 경우에도 O(NlogN)의 시간 복잡도를 갖는다.

 

K가 1부터 시작하므로 K-1번째 원소를 출력한다.

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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());
		ArrayList<Integer> list = new ArrayList<>(N);
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(list);
		System.out.println(list.get(K-1));
	}
}