K번째수 #정렬 #level1

 

💡풀이1 - copyOfRange

public class K번째수 {
	public static void main(String[] args) {
		int[] array = { 1, 5, 2, 6, 3, 7, 4 };
		int[][] commands = { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 } };
		System.out.println("Result: " + Arrays.toString(solution(array, commands)));
	}

	public static int[] solution(int[] array, int[][] commands) {
		int[] answer = new int[commands.length];
		for (int i = 0; i < commands.length; i++) {

			// copyOfRange: 전달받은 배열의 지정된 범위에 해당하는 요소만 새로운 배열로 반환
			int[] temp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
			Arrays.sort(temp);
			System.out.println("Arrays.sort(temp): " + Arrays.toString(temp));

			answer[i] = temp[commands[i][2] - 1];

		}
		return answer;
	}
}

 

 

💡풀이2 - 퀵 정렬

라이브러리를 이용하지 않고 퀵 정렬로 풀이한 코드입니다.

package com.java.programmers;

import java.util.Arrays;

public class K번째수 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] array = {1, 5, 2, 6, 3, 7, 4};
		int[][] commands = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}};
		
		System.out.println(Arrays.toString(solution(array, commands)));
	}

	public static int[] solution(int[] array, int[][] commands) {
		int n = 0;
		int[] ret = new int[commands.length];
		while (n < commands.length) {
			int m = commands[n][1] - commands[n][0] + 1;
			if (m == 1) {
				ret[n] = array[commands[n++][0] - 1];
				continue;
			}
			int[] a = new int[m];
			int j = 0;
			for (int i = commands[n][0] - 1; i < commands[n][1]; i++)
				a[j++] = array[i];
			sort(a, 0, m - 1);
			ret[n] = a[commands[n++][2] - 1];
		}
		return ret;
	}

	private static void sort(int[] a, int left, int right) {
		int pl = left;
		int pr = right;
		int x = a[(pl + pr) / 2];
		do {
			while (a[pl] < x)
				pl++;
			while (a[pr] > x)
				pr--;
			if (pl <= pr) {
				int temp = a[pl];
				a[pl] = a[pr];
				a[pr] = temp;
				pl++;
				pr--;
			}
		} while (pl <= pr);
		if (left < pr)
			sort(a, left, pr);
		if (right > pl)
			sort(a, pl, right);
	}
}