정렬] K번째 수

꼭 이직이 아니더라도 개발자로서 좀 더 가독성 있고, 깔끔한 코드를 작성하기 위해 알고리즘 문제를 하나씩 풀어보려고 합니다. 현재 제 주 언어인 자바 언어로 풀어보며 코드 레벨에서 어떻게 하면 더 깔끔한 코드를 작성할 수 있을지 고민하고, 통과가 되었더라도 계속 개선해나갈 생각입니다. 문제는 프로그래머스에 있는 K번째 수[1]입니다.

 

_____

문제를 풀면서 고민한 지점은 특정 범위의 배열을 복사[2]하기 위해 어떤 API를 사용해야 하는지였다. 검색을 통해 Arrays 클래스의 copyOfRange(...) 메소드를 사용해야겠다고 생각했고, 테스트 케이스에서 두 번째 예인 [4, 4, 1]처럼 첫 번째 인덱스와 마지막 인덱스가 같은 경우 따로 구분해야 한다고 생각해서 아래와 같이 분기해주었다(으나 다른 사람들의 풀이를 보니 굳이). 한편 연습할 때는 테스트 코드를 작성해봐야 할 필요성도 느꼈다.

 

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        final int[] answer = new int[commands.length];
        
        int[] tmp;
        for (int i = 0; i < commands.length; i++) {
            tmp = new int[commands[i][1] - commands[i][0] + 1];
            
            // Arrays.copyOfRange(array, firstIndex, lastIndex); lastIndex는 미포함
            // [5]
            /*
            if ((commands[i][1] - commands[i][0]) == (commands[i][2] - 1)) { // firstIndex == lastIndex
                System.arraycopy(array, commands[i][0] - 1, tmp, 0, 1);
            } else {
                tmp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            }
            */
            tmp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            
            Arrays.sort(tmp); // 오름차순 정렬(만일 내림차순이라면?)
            
            answer[i] = tmp[commands[i][2] - 1];
        }
        
        return answer;
    }
}

 

_____

1.

2. 여기서 객체를 복사한다는 말은 얕은 복사(Shallow copy)가 아닌 깊은 복사(Deep copy)[3]를 의미한다.

3. 깊은 복사의 방법은 아래와 같다[4].

// 방법1. System.arraycopy(...)
// 부분 복사
int[] array1 = {23, 43, 55, 12, 65, 88, 92};
int[] copiedArray1 = new int[3];
System.arraycopy(array1, 2, copiedArray1, 0, 3);

// 방법2. Arrays.copyOf(...) or Arrays.copyOfRange(...)
// 전체 복사
int[] array2 = {23, 43, 55, 12};
int newLength2 = array2.length;
int[] copiedArray2 = Arrays.copyOf(array2, newLength2);

// 부분 복사
int[] array3 = {23, 43, 55, 12, 65, 88, 92};
int[] copiedArray3 = Arrays.copyOfRange(array3, 1, 4);

// 방법3. Object.clone()
int[] array4 = {23, 43, 55, 12};
int[] copiedArray = array4.clone();

4. 하지만 위 방법들을 원시 타입 배열이 아닌 객체 타입 배열(an array of non-primitive object types)에 적용한다면 얕은 복사를 수행한다.

5. Are the indexes in Arrays.copyOfRange correct?

6.

 

_____

참고자료

 

• Baeldung] How to Copy an Array in Java
• GeeksforGeeks] Array Copy in Java
• How to convert List<Integer> to int[] in Java?
  • int[] ↔ Integer[]
  • int[] ↔ Integer[]
•