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

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

11004번: K번째 수

 

11004번 문제에서 2가지 정렬 방식으로 문제를 접근했습니다.

Arrays.sort(), Collections.sort()

 

Java8에서는 Arrays.sort()는 시간 초과가 나오고 Collections.sort()는 문제를 맞혔습니다.

Java11에서는 Arrays.sort()도 맞았다고 나옵니다.

 

시간 복잡도에서 최악의 경우 Arrays.sort()는 O(n^2) 값이 나와 시간 초과가 나옵니다.

Java11에서는 왜 맞았다고 나오는지 이유를 모르겠네요. 아시는 분 댓글 남겨주시면 감사하겠습니다.

 

퀵 정렬을 직접 구현해 본 결과

피봇의 기준을 왼쪽이나, 오른쪽 값을 기준으로 하면 시간 초과가 납니다. 피봇의 기준을 중간값으로 하면 시간 초과가 나지 않습니다.

아마 java8과 java11 버전 차이는 비봇의 기준이 달라지지 않았나 생각됩니다. 혹은 미리 정렬된 걸 확인하는 것 같습니다.

 

저격 데이터가 들어가 있어 시간 초과되는 상황이라, 실제로 저격 데이터를 만들어 테스트를 해보는 방법뿐입니다. 혹은 최악의 시간 복잡도를 알고 있으면 더 좋겠지요.

 

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

 

 

자바 코드

Collections.sort() 사용

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> arr = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(st.nextToken()));
        }
        
        Collections.sort(arr);
        System.out.println(arr.get(K-1));
    }
}