programmers) K번째수

프로그래머스 K번째수

정렬 알고리즘을 공부한 뒤, 연습 문제로 프로그래머스 K번째수 문제를 풀어보았다.

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748
• 사용 언어: Java
• 풀이 시간: 약 24분
• 제한 시간: 30분
• 결과: 성공
• 남은 시간: 약 6분

처음에는 단순히 배열을 자르고 정렬하면 되는 문제라고 생각했다.
하지만 직접 풀어보니 Arrays.copyOfRange() 사용법, 인덱스 처리, 원본 배열 보존 여부가 중요한 문제였다.

---

1. 문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자른 뒤,
자른 배열을 정렬했을 때 k번째에 있는 수를 구하는 문제이다.

문제 흐름

1. array의 i번째부터 j번째까지 자른다.
2. 자른 배열을 정렬한다.
3. 정렬된 배열에서 k번째 값을 구한다.
4. 모든 command에 대해 위 과정을 반복한다.

---

2. 예시로 이해하기

예를 들어 배열이 다음과 같다고 하자.

array = [1, 5, 2, 6, 3, 7, 4]

명령이 다음과 같다면:

[i, j, k] = [2, 5, 3]

처리 과정은 다음과 같다.

단계	설명	결과
1	2번째부터 5번째까지 자르기	[5, 2, 6, 3]
2	자른 배열 정렬하기	[2, 3, 5, 6]
3	3번째 숫자 구하기	5

따라서 이 command의 결과는 5이다.

---

3. 제한사항

항목	조건
array 길이	1 이상 100 이하
array 원소	1 이상 100 이하
commands 길이	1 이상 50 이하
commands의 각 원소 길이	3

입력 크기가 크지 않아서, 각 command마다 배열을 잘라 정렬해도 충분히 통과할 수 있는 문제였다.

---

4. 입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

command별 처리 과정

command	처리 과정	결과
[2, 5, 3]	[5, 2, 6, 3] → [2, 3, 5, 6] → 3번째 수	5
[4, 4, 1]	[6] → [6] → 1번째 수	6
[1, 7, 3]	[1, 5, 2, 6, 3, 7, 4] → [1, 2, 3, 4, 5, 6, 7] → 3번째 수	3

---

5. 풀이 아이디어

이 문제는 크게 세 가지 작업으로 나눌 수 있다.

순서	작업	사용한 Java 문법
1	배열 일부 자르기	Arrays.copyOfRange()
2	자른 배열 정렬하기	Arrays.sort()
3	k번째 값 꺼내기	배열 인덱스 접근

전체 풀이 흐름은 다음과 같다.

commands를 반복한다.
각 command에서 i, j, k를 꺼낸다.
array에서 i번째부터 j번째까지 자른다.
자른 배열을 정렬한다.
정렬된 배열에서 k번째 값을 answer에 저장한다.

---

6. 인덱스 처리

문제에서 말하는 i번째, j번째, k번째는 사람이 세는 방식이라 1부터 시작한다.

하지만 Java 배열 인덱스는 0부터 시작한다.

문제 기준	Java 인덱스 기준
i번째	i - 1
j번째	j - 1
k번째	k - 1

다만 Arrays.copyOfRange()를 사용할 때는 조금 다르게 봐야 한다.

Arrays.copyOfRange(array, start, end)

인자	포함 여부
start	포함
end	포함하지 않음

예를 들어 문제에서 2번째부터 5번째까지 자르고 싶다면:

Arrays.copyOfRange(array, 1, 5)

실제로 가져오는 인덱스는 다음과 같다.

1, 2, 3, 4

즉, 문제 기준으로는 2번째부터 5번째까지가 맞다.

---

7. 처음 헷갈렸던 부분

처음에는 배열을 자르는 방법을 몰라서 Arrays.copyOfRange()를 찾아보았다.

처음 작성한 코드는 아래와 비슷했다.

array = Arrays.copyOfRange(array, i, j + 1);
Arrays.sort(array);
result[indx] = array[k];

이 코드의 문제는 잘라낸 배열을 다시 array에 대입했다는 점이다.

왜 문제가 되었나?

구분	설명
처음 array	원본 배열 [1, 5, 2, 6, 3, 7, 4]를 가리킴
첫 번째 command 처리 후	array가 잘라낸 배열 [5, 2, 6, 3]을 가리킴
정렬 후	array가 [2, 3, 5, 6] 상태가 됨
다음 command 처리 시	원본 배열이 아니라 바뀐 array를 기준으로 자르게 됨

정확히 말하면 원본 배열의 값이 직접 수정된 것은 아니다.
하지만 array라는 변수가 원본 배열 참조를 잃고, 새 배열을 가리키게 된 것이다.

그래서 다음 command부터 결과가 꼬일 수 있다.

---

8. 해결 방법

원본 배열 array는 그대로 두고, 잘라낸 배열을 별도 변수에 저장했다.

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

이렇게 하면 매 command마다 항상 원본 배열을 기준으로 다시 자를 수 있다.

방식	코드	결과
잘못된 방식	array = Arrays.copyOfRange(array, i, j + 1)	array가 원본 배열을 잃어버림
올바른 방식	int[] sliced = Arrays.copyOfRange(array, start, end)	원본 배열은 그대로 유지됨

---

9. 최종 코드

import java.util.*;

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

        for (int idx = 0; idx < commands.length; idx++) {
            int start = commands[idx][0] - 1;
            int end = commands[idx][1];
            int k = commands[idx][2] - 1;

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

            Arrays.sort(sliced);

            answer[idx] = sliced[k];
        }

        return answer;
    }
}

---

10. 코드 설명

코드	설명
int[] answer = new int[commands.length];	command 개수만큼 결과 배열 생성
int start = commands[idx][0] - 1;	문제의 i번째를 Java 인덱스로 변환
int end = commands[idx][1];	copyOfRange()의 end는 미포함이므로 -1하지 않음
int k = commands[idx][2] - 1;	문제의 k번째를 Java 인덱스로 변환
int[] sliced = Arrays.copyOfRange(array, start, end);	원본 배열에서 필요한 구간만 복사
Arrays.sort(sliced);	복사한 배열만 정렬
answer[idx] = sliced[k];	정렬된 배열에서 k번째 값 저장

---

11. 시간복잡도

각 command마다 배열을 자르고 정렬한다.

작업	시간복잡도
배열 자르기	O(L)
배열 정렬	O(L log L)
command 전체 반복	O(M × L log L)

여기서:

• M은 commands의 길이
• L은 잘라낸 배열의 길이

이 문제는 array 길이가 최대 100, commands 길이가 최대 50이므로 이 풀이로 충분히 통과할 수 있다.

---

12. 배운 점

이번 문제를 풀면서 배운 점은 다음과 같다.

배운 내용	정리
배열 자르기	Arrays.copyOfRange()를 사용하면 편하다
인덱스 처리	문제는 1부터 시작하지만 Java 배열은 0부터 시작한다
copyOfRange()의 end	끝 인덱스는 포함되지 않는다
원본 배열 보존	반복해서 원본 배열 기준으로 잘라야 하므로 원본을 덮어쓰면 안 된다
정렬 대상	원본 배열이 아니라 잘라낸 배열을 정렬해야 한다
디버깅 포인트	출력해보면서 실제 잘린 배열을 확인하는 것이 도움이 됐다

---

13. 마무리

이번 문제는 단순한 정렬 문제처럼 보였지만, 직접 풀어보니 배열 인덱스와 원본 배열 보존이 중요했다.

특히 처음에는 잘라낸 배열을 다시 array에 대입하면서 다음 반복에서 기준 배열이 바뀌는 문제가 있었다.
이후 원본 배열은 그대로 두고, sliced라는 새 배열을 만들어 정렬하는 방식으로 수정했다.

이번 풀이를 통해 정렬 문제를 풀 때는 단순히 Arrays.sort()만 생각하는 것이 아니라,
정렬할 대상이 원본 배열인지, 복사본인지를 먼저 확인해야 한다는 점을 배웠다.

다음 정렬 문제를 풀 때도 아래 내용을 먼저 확인해야겠다.

1. 원본 배열을 보존해야 하는가?
2. 정렬할 대상은 원본인가, 복사본인가?
3. 문제의 인덱스와 Java 인덱스가 어떻게 다른가?
4. 정렬 후 몇 번째 값을 꺼내야 하는가?

정렬은 단순히 값을 줄 세우는 작업이 아니라, 문제 풀이를 위한 준비 과정이라는 점을 다시 느낀 문제였다.