[프로그래머스] K번째 수

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

배열을 i번째부터 j번째까지 잘라서 정렬 후 k번째 수를 구하면 되는 간단한 문제이다.

 

딱히 설명할 것이 없으므로 바로 코드를 보도록 하겠다.

 

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int n = 0; n < commands.length; n++) {
            
            int i = commands[n][0];
            int j = commands[n][1];
            int k = commands[n][2];
            
            // i번째 부터 j번째 까지 자르기
            int[] subarr = Arrays.copyOfRange(array, i - 1, j);
            
            // 자른 문자열 정렬하기
            Arrays.sort(subarr);
            
            // k번째 숫자 저장
            answer[n] = subarr[k - 1];
        }
        return answer;
    }
}

시간 복잡도

• O(M*NlogN)

배열을 자르는 시간복잡도: O(N)

정렬: O(NlogN)

이를 commands의 길이인 M번 반복하므로 시간복잡도는 O(M*NlogN)이다.