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

 

코딩테스트 연습 - K번째수 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1.  array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2.  1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3.  2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

접근 방법

우선, 해당 문제를 2개의 큰 부분으로 나눠봤다.

1. 배열 중 일부를 추출하는 부분
2. 추출된 배열을 정렬하는 부분

배열 중 일부를 추출하는 부분은 begin( = i ), end( = j )을 매개변수로 입력받는 cutArray라는 함수를 만들었다.

해당 함수는 j - i + 1 크기를 갖는 배열에 for문을 사용해 원래의 array에서 데이터를 옮겨가는 방식으로 구현했다.

 

정렬에 대해서는 Arrays.sort() 함수를 사용하여 정렬하였다.

1차 코드

import java.util.Arrays;

class Solution {

    public int[] cutArray(int[] array, int begin, int end)
    {
        final int size = end - begin + 1;
        int[] result = new int[size];

        for(int i = 0; i < size; ++i)
        {
            result[i] = array[begin + i];
        }

        return result;
    }

    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i = 0; i < commands.length; ++i)
        {
            int[] cuttedArray = cutArray(array, commands[i][0] - 1, commands[i][1] - 1);

            Arrays.sort(cuttedArray);
            answer[i] = cuttedArray[commands[i][2] - 1];
        }

        return answer;
    }
}

 

코드 자체에는 문제가 없었으나, 코드의 부피를 줄이기 위해 cutArray와 동일하게 동작하는 함수가 없나 찾아보게 되었다.

그래서 찾아보던 중, Arrays.copyOfRange라는 함수를 발견하였다.

• int[] copyOfRange(int[] original, int from, int to) 
  • original에서 [from ~ to)까지의 원소를 복사해 배열 형태로 반환한다.
  • 이 경우, 얕은 복사가 아닌 깊은 복사로 이뤄진다. ( 복사된 값을 변경하여도 원본에는 영향이 가질 않는다. )

해당 함수로 변경하여 다시 구현하였고, 코드는 다음과 같다.

최종 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i = 0; i < commands.length; ++i)
        {
            int[] cuttedArray = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);

            Arrays.sort(cuttedArray);
            answer[i] = cuttedArray[commands[i][2] - 1];
        }

        return answer;
    }
}

 

해당 코드로 작성하였고 통과 되었다.

[ 통과 ]