[프로그래머스] 파트5.7장 정렬 - K번째 수

1. 문제

프로그래머스 - K번째 수

• 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제

2. 초기 풀이

• 배열을 특정 범위로 잘라내기 위해서 Arrays.copyOfRange()를, 정렬하기 위해서 Arrays.sort()를 사용하기로 결정
• commands의 길이는 1부터 50까지 가변적이기 때문에, ArrayList를 활용하여 결과를 구한 뒤 int형 배열로 변환하는 방식으로 문제 해결

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        // k번째에 있는 수를 추가할 result
        List<Integer> result = new ArrayList<>();
        
        // commands의 길이만큼 반복
        for (int i = 0; i < commands.length; i++) {
            int start = commands[i][0];
            int end = commands[i][1];
            int k = commands[i][2];
            
            // 순서와 배열의 인덱스를 맞춰서 array를 잘라낸다
            int[] sliced = Arrays.copyOfRange(array, start - 1, end);
        
            // 정렬
            Arrays.sort(sliced);
        
            // result에 잘라낸 뒤 정렬한 배열의 k번째 수를 추가
            result.add(sliced[k - 1]);
        }
        
        // result를 int형 배열로 변환하여 리턴
        return result.stream()
                     .mapToInt(i -> i)
                     .toArray();
    }
}

3. 개선 풀이

• commands의 길이와 result의 길이는 똑같기 때문에 별도의 ArrayList와 같은 자료구조를 사용하지 않고 바로 int[] 배열을 사용해 리턴하도록 개선

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        // k번째에 있는 수를 추가할 result
        // commands의 길이에 따라 result의 길이가 변하므로 commands의 길이로 초기화
        int[] result = new int[commands.length];
        
        // commands의 길이만큼 반복
        for (int i = 0; i < commands.length; i++) {
            int start = commands[i][0];
            int end = commands[i][1];
            int k = commands[i][2];
            
            // 순서와 배열의 인덱스를 맞춰서 array를 잘라낸다
            int[] sliced = Arrays.copyOfRange(array, start - 1, end);
        
            // 정렬
            Arrays.sort(sliced);
        
            // result에 잘라낸 뒤 정렬한 배열의 k번째 수를 추가
            result[i] = sliced[k - 1];
        }
        
        return result;
    }
}