[Java] 프로그래머스 : k번째 수

https://programmers.co.kr/learn/courses/30/lessons/42748?language=java 

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

 

풀이

commands.length만큼 반복문을 돌린다.

새로운 int 배열 arr에 coomand[i][1]번째부터 command[i][0]번째 원소를 복사하고 정렬시킨다.

arr 에서 k번째 수인 command[i][2]-1번째 원소 구해 answer[i]에 넣어준다.

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for (int i=0; i< commands.length ; i++){         
            int[] arr = new int[commands[i][1]-commands[i][0]+1];
            int c = 0;
            for(int j=commands[i][0]-1; j<commands[i][1]; j++){                
                arr[c]=array[j]; c+=1;
            }
            Arrays.sort(arr);
            answer[i]=arr[commands[i][2]-1];
        }
        return answer;
    }
    
}

 

정렬 직접 구현

위에선 정렬을 라이브러리로 했었는데 정렬문제니 직접 구현해보는것도 좋다고 생각한다.

퀵소트(Quick sort)를 구현한 함수 sort()를 정의해 정렬을 한 코드이다.

복사한 배열의 가운데 요소를 pivot으로 줘서 pivot을 기준으로 정렬을 한다.

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for (int i=0; i< commands.length ; i++){         
            int[] arr = new int[commands[i][1]-commands[i][0]+1];
            int c = 0;
            for(int j=commands[i][0]-1; j<commands[i][1]; j++){                
                arr[c]=array[j]; c+=1;
            }
            sort(arr,0,commands[i][1]-commands[i][0]);
            answer[i]=arr[commands[i][2]-1];
        }
        return answer;
    }
    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 tmp = a[pl];
                a[pl] = a[pr];
                a[pr] = tmp;
                pl++;
                pr--;
            }
        }while(pl<=pr);
            
        if(pr>left) sort(a,left,pr);
        if(pl<right) sort(a,pl,right);
    }
}

 

+ 참고

배열을 복사하는 라이브러리 함수에는 copyOfRange()가 있다.

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