프로그래머스 [k번째 수] - 42748

문제 링크입니다.

코딩테스트 연습 - K번째수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - K번째수

 

이 문제는 수를 정렬하는 것이 다입니다.

다만 여기서 중요한 포인트는 '시간' 인데요!

 

정렬을 어떻게 하느냐에 따라 시간복잡도가 달라지기 때문에, 코드를 잘 짜야 합니다. 문제의 제한사항을 봅시다.

 

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

 

정답 소스코드

public int[] solution(int[] array, int[][] commands) {
    int[] answer = new int[commands.length];

    for(int i=0;i< commands.length;i++){ // O(N)
        int start = commands[i][0];
        int end = commands[i][1];
        int k = commands[i][2];

        List<Integer> temp = new ArrayList<>(); int idx = 0;

        for(int j = start-1 ; j <= end-1 ; j++){ // O(N)
            temp.add(array[j]);
        }
        Collections.sort(temp);

        answer[i] = temp.get(k-1);
    }

    return answer;
}

 

 

정렬을 하는 부분을 봅시다.

Collections.sort() 함수의 시간복잡도 =  O(N*logN)으로,

최선의 경우와 최악의 경우 모두 N*log(N)으로 동일합니다.

 

정렬에는 자바에서 java.util.Arrays 클래스에서 지원하는 Arrays.sort() 함수도 있습니다.

하지만 Arrays 클래스에서 지원하는 정렬은 최악의 경우 O(N^2) 이 될 수도 있습니다.

 

(Sort 함수의 시간복잡도 분석은 정렬에 관한 포스팅에서 더욱 심도있게 다루도록 하겠습니다.)

 

이렇게 정렬된 배열 temp를 가지고 k값에 따라 정답 배열에 하나씩 추가해주기만 하면 끝입니다.