[Java] 프로그래머스 - K번째 수

주어진 구간을 잘라 정렬한 뒤, 그 안에서 K번째 수를 구하는 문제

 

1. 문제 유형

배열, 정렬, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 각 명령어마다 배열의 i번째부터 j번째까지 잘라서 새로운 배열을 만들고, 정렬한 뒤 k번째 값을 answer 배열에 넣는 방식으로 접근했다.

오답 원인: Arrays.copyOfRange()의 끝 인덱스가 포함이 아니라 제외라는 점을 놓쳤다.
그래서 commands[i][1] - 1을 넣어 마지막 값이 잘렸고, [4, 4, 1] 같은 경우에는 빈 배열이 만들어져 인덱스 에러가 발생했다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 문제의 구간은 i번째부터 j번째까지처럼 끝 값이 포함되는 범위로 주어진다.
하지만 Arrays.copyOfRange(arr, from, to)는 from 이상 to 미만 범위만 복사한다.

풀이 아이디어:

1. copyOfRange(array, 시작인덱스, 끝인덱스+1개념)으로 부분 배열을 만든다.
2. 부분 배열을 정렬한다.
3. k-1 인덱스의 값을 answer에 저장한다.

4. 구현 코드

import java.util.*;

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

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

        return answer;
    }
}

시간 복잡도: O(N x M log M) / 공간 복잡도: O(N + M)

---

 

인사이트

• copyOfRange()는 끝 인덱스를 포함하지 않는다는 점을 정확히 알고 써야 한다.
• 배열 자르기와 정렬 자체는 어렵지 않았지만 이런 경계값 처리 실수가 구현 문제에서 가장 자주 틀리는 부분이라는 걸 다시 느꼈다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42748