프로그래머스 - K번째 수

문제 설명

배열 array와 commands가 주어질 때, commands의 각 행 [i, j, k]에 대해 array의 i번째부터 j번째까지 자르고 정렬한 뒤 k번째 수를 구하는 문제이다.

array    = [1, 5, 2, 6, 3, 7, 4]
commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

[2, 5, 3] → 2번째~5번째 자르기 → [5, 2, 6, 3] → 정렬 → [2, 3, 5, 6] → 3번째 → 5
[4, 4, 1] → 4번째~4번째 자르기 → [6]           → 정렬 → [6]           → 1번째 → 6
[1, 7, 3] → 1번째~7번째 자르기 → [1,5,2,6,3,7,4] → 정렬 → [1,2,3,4,5,6,7] → 3번째 → 3

---

접근 방법

1. commands를 하나씩 순회하면서 [i, j, k] 값을 꺼내기
2. array에서 i번째~j번째 구간을 자르고 정렬
3. k번째 수를 결과 배열에 저장
   Java에서 배열의 특정 구간을 자를 때는 Arrays.copyOfRange()를 사용한다.
   

Arrays.copyOfRange(array, from - 1, to)

문제에서는 인덱스가 1부터 시작하기 때문에 -1을 붙여준다.

from = 2 → 인덱스 1 → from - 1
to   = 5 → 인덱스 4까지 포함 → copyOfRange 끝은 포함 안 되므로 to 그대로
k    = 3 → 인덱스 2 → k - 1

정렬은 Arrays.sort()로 오름차순 정렬한다.

구체적으로 정리한 풀이 흐름:

1. commands 길이만큼 반복문 실행
2. commands[i][0], commands[i][1], commands[i][2]로 from, to, k 추출
3. Arrays.copyOfRange(array, from - 1, to)로 구간 자르기
4. Arrays.sort(slice)로 정렬
5. slice[k - 1]로 k번째 수 추출 후 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 from = commands[i][0];
            int to   = commands[i][1];
            int k    = commands[i][2];
 
            // 1. 자르기
            int[] slice = Arrays.copyOfRange(array, from - 1, to);
 
            // 2. 정렬
            Arrays.sort(slice);
 
            // 3. k번째 수 저장
            answer[i] = slice[k - 1];
        }
 
        return answer;
    }
}

---