프로그래머스 - K번째수 java :: 정렬

42748번

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

프로그래머스

---

풀이

▶ 주의할 점

✔ i, j, k 모두 인덱스보다 1이 크다.

✔ i와 j로 새로 만든 배열을 정렬 후 k번째 수를 구해야 한다.

 

• 풀이1

public int[] solution(int[] array, int[][] commands) {
	int[] answer = new int[commands.length];
	
	for(int m = 0; m<commands.length; m++) {
		int i = commands[m][0];
		int j = commands[m][1];
		int k = commands[m][2];
		
		int[] slices = Arrays.copyOfRange(array, i-1, j);
		Arrays.sort(slices);
		answer[m] = slices[k-1];
	}
	return answer;
}

✅ public static int[] copyOfRange(int[] original, int from, int to)

배열 original에서 from부터 to까지의 요소를 복사해 새로운 배열을 만든다.

✅ public static void sort(int[] a)

배열을 오름차순 정렬한다.

 

정렬 후 k번째 수를 정답 배열에 저장한다.

 

✔ 테스트 케이스 처리속도: 평균 0.35ms

 

• 풀이2

public int[] solution(int[] array, int[][] commands) {
	int answer[] = new int[commands.length];
	
	for(int m=0; m<commands.length; m++) {
		int i = commands[m][0];
		int j = commands[m][1];
		int k = commands[m][2];
		
		int[] slices = new int[j-i+1];
		int idx = 0;
		for(int a=i-1; a<j; a++) slices[idx++] = array[a];
		
		for(int o1=0; o1<k; o1++) {
			for(int o2=o1+1; o2<slices.length; o2++) {
				if(slices[o1] > slices[o2]) {
					int tmp = slices[o1];
					slices[o1] = slices[o2];
					slices[o2] = tmp;
				}
			}
		}
		
		answer[m] = slices[k-1];
	}
	
	return answer;
}

자바의 라이브러리를 활용하니까 너무 쉽게 푼 것 같아서 라이브러리 없이도 풀고 싶었습니다.

처리속도도 당연히 올라갈 것 같았구요.

 

✅ int[] slices

i부터 j까지의 요소를 담을 배열

 

선택정렬로 오름차순 정렬을 진행합니다.

단, k번째 수를 구하는 것이므로 인덱스는 k까지만 정렬하면 됩니다. k보다 높은 인덱스의 정렬은 필요없습니다.

만약 k=1 인데 배열의 길이는 100일 경우를 예를 들면 제일 작은 수 1개만 구하면 되는데 배열 전체를 다 정렬 후 제일 작은 수를 가져오면 너무 큰 손해이기 때문입니다.

 

✔ 테스트 케이스 처리속도: 0.01ms ~ 0.02ms