프로그래머스 > 정렬 > K번째수

 

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

array	commands [[i,j,k],[i,j,k]..]	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

public static int[] solution(int[] array, int[][] commands) {
	    int[] answer = new int[commands.length];
	    int idx = 0;
	    for(int i=0;i<commands.length;i++) {
	    	int start = commands[i][0]-1;
	    	int end = commands[i][1]-1;
	    	int order = commands[i][2];
	    	int length = end  - start +1;
	    	int [] nums = new int[length];
	    	int index = 0;
	    	for(int j=start;j<=end;j++) {  
	    		nums[index++] = array[j];
	    	}
	    	Arrays.sort(nums);
	    	answer[idx++] = nums[order-1];
	    }
	    return answer;
	}

다른 사람의 더 간결한 코드 Arrays.copyOfRange 사용

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

        for(int i=0; i<commands.length; i++){
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }

 public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int a = 0;
        for(int[] info : commands){
            int i = info[0];
            int j = info[1];
            int k = info[2];

            int[] buf = Arrays.copyOfRange(array,i-1,j);
            Arrays.sort(buf);
            answer[a] = buf[k-1];
            a++;
        }

        return answer;
    }

 

 

다른 사람이 직접 짠 정렬 코드 

- 시작과 끝의 길이가 1일 때 하나만 넣고 바로 넘어가는 것.

- 시작부터 끝까지 임의의 배열 a에 넣고 sort 함수 호출 

public 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;
    }

    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);
    }