k번째 수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748

문제 요약

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구한다. commands의 각 원소는 [i, j, k]이고, 이 연산을 모든 command에 대해 적용한 결과를 배열로 반환해야 한다.

첫 번째 풀이

import java.lang.StringBuilder;
import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        int start = 0;
        int end = 0;
        int target = 0;
        int answerCnt = 0;

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

            start = commands[i][0] - 1;
            end = commands[i][1] - 1;
            target = commands[i][2] - 1;
            int cnt = 0;

            int[] tempArr = new int[(end - start + 1)];

            System.out.println(tempArr.length);

            for (int j = start; j <= end; j++) {
                tempArr[cnt] = array[j];
                cnt++;
            }

            Arrays.sort(tempArr);

            for (int k = 0; k < tempArr.length; k++) {
                if (k == target) {
                    answer[answerCnt] = tempArr[k];
                    answerCnt++;
                }
            }
        }
        return answer;
    }
}

처음에 놓쳤던 부분

• i, j, k를 1-indexed에서 0-indexed로 바꾸는 것까지는 맞게 했지만, 배열을 직접 인덱스로 자르는 대신 반복문을 돌려서 하나씩 옮겨 담았다 (tempArr[cnt] = array[j]).
• 정렬된 배열에서 target 위치의 값을 꺼낼 때도 처음부터 끝까지 순회하면서 k == target을 비교하는 방식으로 짰다. 정렬된 배열은 인덱스로 바로 접근 가능한데 이 사실을 활용하지 못했다.
• answerCnt라는 변수를 따로 만들어서 관리했는데, 사실 바깥쪽 반복문의 i와 같은 값이라 불필요한 변수였다.
• 디버깅용 System.out.println을 정리하지 않고 그대로 뒀다.

개선한 풀이

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 start = commands[i][0] - 1;
            int end = commands[i][1];
            int target = commands[i][2] - 1;

            int[] temp = Arrays.copyOfRange(array, start, end);
            Arrays.sort(temp);

            answer[i] = temp[target];
        }
        return answer;
    }
}

어떻게 바꿨는지

1. 배열을 수동으로 복사하던 반복문을 Arrays.copyOfRange(array, start, end)로 대체했다.
2. 정렬된 배열에서 target 값을 찾는 반복문도 없앴다. target 인덱스를 이미 알고 있으니 temp[target]으로 바로 접근하면 된다.
3. answerCnt 대신 바깥 반복문의 i를 그대로 사용해서 변수를 줄였다.

알게 된 개념: copyOfRange의 from/to 규칙

Arrays.copyOfRange(array, from, to)는 from은 포함, to는 포함하지 않는(half-open interval) 규칙을 따른다. String.substring(from, to), List.subList(from, to)도 동일한 규칙이다.

이렇게 만든 이유:

• to - from이 곧 잘라낸 배열의 길이가 된다. 예를 들어 인덱스 1~4 (4개 원소)를 뽑고 싶으면 copyOfRange(array, 1, 5)처럼 써야 하고, 5 - 1 = 4로 개수가 딱 맞아떨어진다.
• 만약 to도 포함이었다면 길이를 구할 때마다 to - from + 1을 계산해야 해서 off-by-one 실수가 나기 쉽다.
• 구간을 이어붙일 때도 [0,3)과 [3,6)처럼 겹치거나 빠지는 부분 없이 자연스럽게 연결된다.

그래서 문제의 j번째(1-indexed, inclusive)까지 자르려면 배열 인덱스로는 j-1까지 필요한데, copyOfRange의 to는 exclusive이므로 j-1+1 = j, 즉 commands[i][1]을 그대로 넣으면 된다.

곁다리로 확인한 것: Comparator와 primitive 타입

풀이를 정리하다가 Arrays.sort(temp, (o1, o2) -> o1 - o2)처럼 Comparator를 써서 정렬하면 어떻게 되는지 궁금해서 짚어봤다.

• compare(o1, o2)가 음수를 반환하면 o1이 o2보다 앞에 온다. o1 - o2는 o1 < o2일 때 음수이므로, 이 Comparator는 오름차순 정렬이 된다.
• 다만 Arrays.sort(배열, Comparator) 형태는 int[] 같은 primitive 타입 배열에는 쓸 수 없다. Comparator는 인터페이스이고 인터페이스는 객체(Object)에만 적용되는데, int는 객체가 아니기 때문이다.
• 따라서 temp가 int[]라면 커스텀 Comparator 없이 그냥 Arrays.sort(temp)만 써도 충분하다 (기본 동작이 오름차순). 굳이 Comparator로 커스텀 정렬을 하고 싶다면 Integer[]로 박싱해서 선언해야 한다.

정리

• 배열을 자르고 정렬해서 특정 위치 값을 구하는 문제는 Arrays.copyOfRange + Arrays.sort + 인덱스 직접 접근으로 충분히 간결하게 풀린다.
• copyOfRange, substring, subList 등 Java의 범위 관련 API는 "from 포함, to 미포함" 규칙을 공통으로 따른다는 걸 기억해두면 좋다.
• Comparator 기반 정렬은 객체 타입에서만 동작하므로, primitive 배열을 커스텀 정렬하려면 Wrapper 타입(Integer[])으로 바꿔야 한다.