Programmers - 정렬 [K번째 수]

1. 문제

문제 설명

배열 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]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

2. 내 풀이

import java.util.*;

public class KthNumber {
    public int[] solution(int[] array, int[][] commands) {
        // 답으로 제출될 answer 배열은 commands.length와 길이가 같다.
        int[] answer = new int[commands.length];
        // commands배열의 이중배열의 길이만큼 반복된다.
        for (int i = 0; i < commands.length; i++) {
            // 이중배열의 값은 각각 I, J ,K로 저장되고 I부터 J까지 배열을 생성한후 정렬하고 그 배열의 K번쨰 원소를 저장한다.
            for (int j = 0; j < commands[i].length; j++) {
                // I, J ,K는 index형식이 아니라서 -1을 해주어 배열에 대입하기 쉽게 바꿔준다.
                int I = commands[i][0] - 1;
                int J = commands[i][1] - 1;
                int K = commands[i][2] - 1;
                // I부터 J까지 짤린 배열을 만든다.
                int[] tmpArr = new int[J - I + 1];
                for (int k = 0; k < J - I + 1; k++) {
                    tmpArr[k] = array[I + k];
                }
                // 정렬
                Arrays.sort(tmpArr);
                answer[i] = tmpArr[K];
            }
        }
        return answer;
    }

    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}};
        KthNumber kthNumber = new KthNumber();
        System.out.println(kthNumber.solution(array, commands));
    }
}

- 오류 없이 한번에 풀었다;

- 원래 python으로 한번 풀었던 문제라서 그런가 오류 없이 한번에 클린코딩 했다.

리뷰하면서 보니 딱히 문제가 있는 코드는 아니었다.

다만 배열에는 기본적으로 들어가 있는 정렬 메소드는 없기 때문에

Arrays.sort()라는 메소드를 사용했다.

3. 다른 사람 풀이

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[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }
}

- 비슷한 풀이이나 Arrays.copyRange 메소드를 사용했다. 

- 메소드를 보면 copyOf라는 메소드가 있는데 0 부터 길이만큼 복사해서 넘기는 메소드가 있고

- copyOfRange라는 메소드는 어디부터 어디까지 복사해서 넘기는 메소드이다. 

인수를 살펴보면 실제 인덱스값을 넘기는 것이기 때문에 copyOfRange(arr, i , j)라고 한다면

arr = {1 ,2 ,3, 4, 5}라면 arr[i] 부터 arr[j - 1]사이를 정렬한다. 실제 배열에 넘겨지는 값은 i , j -1 인것을 생각해서

인수를 넣어야한다.

 

4. Tip

- 배열을 정렬하는 Arrays.sort()는

여러 인수가 있었는데, 요약하자면 sort(배열, N 인덱스부터, M 번째 까지)

즉, 배열 sort(arr, 1, 3)을 인수로 받고 arr = {1 ,2 ,3, 4, 5}라면 

arr[1] 부터 arr[2]사이를 정렬한다.