K번째 수 (프로그래머스) [JAVA]

 

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42748

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

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

 

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

 

풀이

완전 단순하게 풀었다.
새 배열에 잘라서 넣고 -> 기본함수로 정렬하고 -> 결과 뽑아내는 과정을 for문을 통해 반복했다.
JAVA의 기본 정렬은 머지, 퀵을 혼합한 방식이므로 $O(NlgN)$,
여기서 Command만큼 반복했으므로 전체 시간복잡도는 $O(N^2lgN)$이라고 생각한다.
다른 사람들의 풀이를 보다 배열을 잘라내는 것을 자바에서 기본함수로 지원하는 것을 알게되었다.

int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);

 

코드

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
       for(int y=0; y<commands.length; y++){
    	   
    	   int start = commands[y][0];
    	   int end = commands[y][1];
    	   int index = commands[y][2];
    	   
    	   int[] sample = new int[end-start+1];
    	   //배열 잘라내기
    	   for(int i=0; i< end-start+1; i++){
    		   sample[i] = array[start+i-1];
    	   }
    	   
    	   Arrays.sort(sample);//정렬
    	   answer[y] = sample[index-1];//추출
       }
        return answer;
    }
}

 

결과

 

복기

블로그에는 올리지 않았지만 백준의 국회의원 선거라는 문제를 풀면서, 자바의 정렬방법에 대해 간략하게 정리해놓은 것이 있다.

Collection.sort 는 자바의 기본 오름차순 정렬 라이브러리인데 다음과 같은 복잡도를 가진다고 한다.

예전 : InsertionSort, Merge Sort, Quick Sort
현재 : Tim Sort, Dual-Pivot Quick Sort
예전에는 배열의 크기가 7개 미만일때 삽입정렬, 7개 이상일때 MergeSort를 썼다.
그리고 Primitive Type Array(기본 자료형) 일때는 같은 값이 서로 순서가 바뀌어도 상관이 없으므로, (Not Stable 하게 해도 됨)
값에 대한 비교가 많더라도 Array에 대한 Access횟수가 적어 더 빠른 Quick Sort를 사용하였다.
Quick Sort는 정렬을 하면서 분할하고 마지막에 정렬, Merge Sort는 쪼개질대로 다 나누고 이를 합치면서 정렬
하지만 Quick Sort는 $nlgn$을 보장하지 않지만, Merge Sort는 $nlgn$을 보장해줌.
하지만 Object Array(객체)일때는 각각 주소가 있어서 비교값이 같다고 하더라도 엄연히 다른 것이다. (Stable 하게 해야함)
따라서 Stable한 정렬중 빠른 Merge Sort를 사용하였다.
하지만 현재는 Insertion Sort와 Merge Sort가 합쳐진 Tim Sort와 (stable)
Quick Sort에서 업그레이드 된 Dual-pivot Quick Sort를 사용한다. (Not stable)