k번째수

문제정의

---

배열이 주어지고 명령어가 들어올 때 해당하는 숫자들을 배열에 모아 반환해야 한다. 명령어는 총 3부분인데 [i, j, k]라고 하면 배열의 i에서 j번째까지 자른 다음에 이를 정렬한다. 그리고 이 부분 배열중에서 k번째 숫자를 고르면 된다.

문제풀이

---

부분 배열을 얼마나 잘 만드는가의 문제인데 자바같은 경우 이미 라이브러리가 존재한다(그래서 1점밖에 득점을 못했나..). 논리자체는 어렵지 않다. 문제에서 요구하는 사항을 그대로 따라가면 된다.

전체 코드는 다음과 같다.

import java.util.*;

public class KthNum {
    
    public static void main(String[] args)
    {
        int[] array = {1, 5, 2, 6, 3, 7, 4};
        int[][] commands = {
            {2, 5, 3},
            {4, 4, 1},
            {1, 7, 3}
        };
        ArrayList<Integer> num = new ArrayList<Integer>();
        for(int i = 0; i < commands.length; i++)
        {
            int[] subarr = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(subarr);
            num.add(subarr[commands[i][2]-1]);
        }
        int[] answer = new int[num.size()];
        for(int i = 0; i < num.size(); i++)
        {
            answer[i] = Integer.parseInt(num.get(i).toString());
            //System.out.print(answer[i]);
        }
    }

}

부분부분 살펴보자

ArrayList<Integer> num = new ArrayList<Integer>();
for(int i = 0; i < commands.length; i++)
{
    int[] subarr = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
    Arrays.sort(subarr);
    num.add(subarr[commands[i][2]-1]);
}

부분배열 subarr를 만들기위해 copyOfRange를 사용한다. copyOfRange의 경우 [i,j)이기 때문에 i-1을 입력해야한다. 배열은 0부터 시작한다. 잊지말자. end부분에는 -1할 필요가 없다. 애초에 포함이 안된다. 그 다음 부분배열을 정렬해주고 k번째에 해당하는 수는 num에 넣어준다. 이 부분에서 시간복잡도는 일단 commands의 길이를 m이라하고 array의 길이를 n이라고 한다면, \(O(mnlogn)\)이 된다. i와 j로인해 잘리는 최대 크기가 n이기 때문이다. copyOfRange에서 \(O(n)\)의 시간이 걸리고 sort에서 \(O(nlogn)\)의 시간복잡도를 가진다. add는 \(O(1)\)이다.

테스트

이번 포스팅은 문제의 요구사항을 그대로 코드로 옮기는 것이라 그렇게 어려운 부분이 없다. 하지만 여전히 Integer를 int로 바꾸는 것은 익숙치 않다.