[C#] K번째 수

K번째 수

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때,
commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

풀이

문제 설명 보충

• 문제에서 제공하는 설명에서 부족함이 있어 풀이에 혼란이 있었기에 설명을 보충한다.

  제공되는 commands : [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

• 해당 정보로는 commands가 int[][]인 int 배열의 배열 형태로 보인다.
  그러나 Solution 함수에서 제시되는 구조는 int[,] 다차원 배열이다.

  실제 입력되는 commands : new int[3, 3] { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 } };

• 실제로는 위와 같은 형태로 입력되는 것에 유의하며 문제를 풀이하도록 하겠다.

Solution 함수

    public int[] Solution(int[] array, int[,] commands)
    {
        int commandsLength = commands.GetLength(0);
        
        int[][] answerSet = new int[commandsLength][];
        int[] answer = new int[commandsLength];
        
        for (int i = 0; i < commandsLength; i++)
        {
            int start = commands[i, 0];
            int end = commands[i, 1];
            int k = commands[i, 2];
            
            answerSet[i] = GetSubArray(array, start, end);
            answer[i] = answerSet[i][k-1];
        }
        
        return answer;
    }

• Solution 함수 자체는 commands의 배열의 크기에 따라 특정 구간을 자른 배열을 담을 answerSet int 배열의 배열을 선언하고, 정답이 될 answer 배열을 선언한다.
• 이후 commands 성분에서 start, end, k 성분을 가져와 GetSubArray 함수에 전달한다.
  해당 함수에서는 array를 특정 구간만큼 자르고 정렬하여 반환한다.
• 이후 입력받은 answerSet에서 k번째 숫자를 찾아 answer에 추가한다.

GetSubArray 함수

private int[] GetSubArray(int[] array, int startIndex, int endIndex)
    {
        int actualStartIndex = startIndex - 1;
        int actualEndIndex = endIndex - 1;
    
        int length = actualEndIndex - actualStartIndex + 1;
        int[] subArray = new int[length];

        Array.Copy(array, actualStartIndex, subArray, 0, length);
    
        int[] sortedSubArray = QuickSort.Sort(subArray);
    
        return sortedSubArray;
    }

• 입력받은 start와 end는 1부터 시작하도록 설정되어 있으므려 1을 빼, 배열의 인덱스처럼 0부터 시작하는 구조로 바꿔준다.
• start와 end에 맞춘 배열의 크기를 설정하고 입력 받은 배열을 특정 구간만큼 복사해 subArray를 만들어준다.
• 이후 subArray를 QuickSort 방식으로 정렬해 반환한다.