[Camel][Java] 알고리즘 문제 해결 - 정렬(Sort) / copyOfRange

문제 내용 설명에 앞서 문제는 프로그래머스에서 풀이한 문제임을 알립니다.

 

문제 내용

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

 

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

 

예시

array = {1, 5, 2, 6, 3, 7, 4},

commends ={ {2,5,3}, {4,4,1} ,{1,7,3} }이라면

 

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

 

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

 

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

위의 결과를 토대로 solution 함수는 {5, 6, 3} 을 반환하게됩니다. 

 

 

문제 해결

문제 내용을 확인해보면 위 문제는 매우 간단한 정렬문제임을 확인할 수 있습니다. 

정렬의 경우에는 아래와 같이 직접 구현할 수도 있습니다. 

void quickSort(int[] a, int left, int right){
  int pl = left;
  int pr = right;
  int x = a[(pl+pr)/2];

  do{
    while(a[pl] < x) pl++;
    while(a[pr] > x) pr--;
    
    if(pl <= pr){
      int temp = a[pl];
      a[pl] = a[pr];
      a[pr] = temp;
      pl++;
      pr--;
    }
  }while(pl <= pr);

  if(left < pr) quickSort(a, left, pr);
  if(right > pl) quickSort(a, pl, right);
}

 

다른 방법으로는 Java에서 제공하는 함수를 사용하는 방법이 있습니다. 사용방법은 아래와 같이 매우 간단합니다. 

import java.util.Arrays;

Arrays.sort(arrayName);

 

그렇다면 이제 위의 정렬을 사용해서 문제를 해결해보면 아래와 같은 Solution 함수를 작성할 수 있습니다. 

 

문제 정답 1.

import java.util.Arrays;

public static int[] solution(int[] array, int[][] commands) {
    int cmdLength = commands.length;

    int[] answer = new int[cmdLength];

    for(int i=0; i<commands.length; i++) {

        int first = commands[i][0];
        int second = commands[i][1];
        int third = commands[i][2];
        int tempLength = second-first+1;

        int[] temp = new int[tempLength];

        for (int j = 0; j < second - first + 1; j++) {
            temp[j] = array[second-j-1];
        }
        Arrays.sort(temp);
        answer[i] = temp[third - 1];

    }

    return answer;
}

 

하지만 여기서 추가적으로 코드를 간결하게 하고싶다면,  배열의 특정 범위를 복사하고자할때 사용하는 함수가 있습니다. 바로 copyOfRange 메소드입니다. 

 

copyOfRange 메소드

copyOfRange() 메소드는 전달받은 배열의 특정 범위에 해당하는 요소만을 새로운 배열로 복사하여 반환합니다. copyOfRange() 메소드는 첫 번째 매개변수로 복사의 대상이 될 원본 배열을 전달받습니다. 두 번째 매개변수로는 원본 배열에서 복사할 시작 인덱스를 전달받고, 세 번째 매개변수로는 마지막으로 복사될 배열 요소의 바로 다음 인덱스를 전달받습니다. 즉, 세 번째 매개변수로 전달된 인덱스 바로 전까지의 배열 요소까지만 복사됩니다. 그리고 원본 배열과 같은 타입의 복사된 새로운 배열을 반환합니다.

 

copyOfRange 함수를 사용해 위의 문제를 해결해보면 아래와 같이 간결하게 함수를 구현할 수 있습니다.

 

문제 정답 2.

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

    for(int i=0; i<commands.length; i++){
        int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
        Arrays.sort(temp);
        answer[i] = temp[commands[i][2]-1];
    }

    return answer;
}