프로그래머스 > 고득점kit > 정렬 > K번째 큰 수 - JAVA

문제 설명

배열 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입니다.

입출력 예

arraycommandsreturn

[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입니다.

---

코드

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length]; //commands의 row 값만큼 배정
        
        for(int i = 0; i < commands.length; i++) //commands의 row 값만큼 반복
        {
            int how = (commands[i][1] - commands[i][0]) + 1; // n1~n2까지의 길이를 배정
            int[] temp = new int[how]; // n1~n2까지를 임시로 저장해줄 배열
            int count =0;
            for(int j = commands[i][0]-1; j <= commands[i][1]-1; j++) //n1~n2까지 
            {
                temp[count] = array[j]; //임시저장
                count++; //temp의 좌표 이동
            }
            Arrays.sort(temp); //정렬
            answer[i] = temp[commands[i][2]-1]; //저장
        }
        return answer;
    }
}

 

---

의도

 단순하게 생각했다. commands[i][0]-1 번째부터 commands[i][1]-1 번째 까지의 수를 임시 배열(temp)에 저장한 후 오름차순으로 정렬 후 commands[i][2]-1 번째의 수를 구하면 되는 문제였다.

1. answer에 필요한 길이는 commands 배열의 행(row)의 길이와 같으므로, commands.length 만큼 배정해준다.

2. for문(또는 다른 반복문)에서 필요한 반복 횟수도 위와 같다.

3. n1부터 n2까지의 값을 임시로 저장할 배열(temp)을 생성.

4. temp에 n1부터 n2까지의 값을 저장 후 정렬.

5. answer에 commands[i][2]-1번째의 array값을 저장.

---

결과

---

다른 사람의 코드

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

 

copyOfRange 써서 코드를 단축시켰다. 근데 실행시간은 그렇게 달라지지 않는다.

 

class Solution {
    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);
    }
}

이 분은 sort 부분을 함수로 직접 구현하셨고 copyOfRange도 직접 구현하셨다.