[프로그래머스] K번째 수 풀이 (정렬)

문제 소개

오늘 풀었던 프로그래머스 - K번째 수 문제를 정리합니다.

이 문제는 주어진 배열에서 특정 구간을 잘라 정렬한 후, k번째 수를 구하는 작업을 반복하는 문제입니다.

문제 링크: K번째 수 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 주어진 commands 배열을 순회합니다.
2. 각 명령어마다 array의 일부를 잘라 복사합니다. (Arrays.copyOfRange 사용)
3. 복사한 배열을 오름차순 정렬합니다.
4. 정렬된 배열에서 k번째 숫자를 찾아 결과 배열에 저장합니다.

---

해결 과정 및 코드

핵심 아이디어

1. copyOfRange를 통해 배열을 잘라낸다. (i-1부터 j까지)
2. 잘라낸 배열을 정렬한다.
3. k번째 요소(k-1 인덱스)를 결과 배열에 저장한다.

코드

시간 복잡도 : O(M × N log N)

• M은 명령어(commands) 수 (최대 50)
• N은 잘라낸 배열의 길이 (최대 100)
• 잘라낸 배열을 매번 정렬하기 때문에, 최악의 경우 M × N log N의 시간 복잡도

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int cmdCnt = commands.length;
        int[] answer = new int[cmdCnt];
        for (int i = 0; i < cmdCnt; i++) {
        	// i ~ j 부분 배열 복사 j 부분 배열 복사 (깊은 복사)
            int[] arr = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            Arrays.sort(arr); // 정렬
            answer[i] = arr[commands[i][2] - 1];
        }
        return answer;
    }
}