[프로그래머스] k번째수 (자바)

코드

 

package psg.고득점킷트.정렬;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class PSG_K번째수 {

    public static void main(String[] args) {
        PSG_K번째수 psgK번째수 = new PSG_K번째수();
        int[] solution = psgK번째수.solution(new int[]{1, 5, 2, 6, 3, 7, 4}, new int[][]{{2, 5, 3}, {4, 4, 1}, {1, 7, 3}});
        System.out.println(Arrays.toString(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;  // 1-based index를 0-based index로 변환
            int end = commands[i][1] - 1;    // 1-based index를 0-based index로 변환

            List<Integer> list = new ArrayList<>();
            // 원하는 수 담기
            for (int j = start; j <= end; j++) {
                list.add(array[j]);
            }
            // 오름차순 정렬
            list.sort(Comparator.comparing(Integer::intValue));

            int k = commands[i][2] - 1;  // 1-based index를 0-based index로 변환
            answer[i] = list.get(k);
        }

        return answer;
    }
}

시간 복잡도 분석

• 부분 배열 생성: O(n) (여기서 n은 end - start + 1입니다)
• 정렬: O(m log m) (여기서 m은 부분 배열의 길이입니다)
• 총 시간 복잡도: O(q * m log m) (여기서 q는 commands의 길이, m은 평균적으로 명령어에 의해 잘라낸 배열의 길이입니다)

테스트 케이스

arraycommandsExpected OutputExplanation

[1, 5, 2, 6, 3, 7, 4]	{{2, 5, 3}, {4, 4, 1}, {1, 7, 3}}	[5, 6, 3]	각 명령어에 대한 결과는 [5, 6, 3]입니다.
[1, 2, 3, 4, 5]	{{1, 3, 2}, {2, 4, 1}, {1, 5, 4}}	[2, 2, 4]	각 명령어에 대한 결과는 [2, 2, 4]입니다.
[5, 4, 2, 1, 3]	{{2, 5, 2}, {1, 3, 1}, {2, 4, 3}}	[2, 4, 1]	각 명령어에 대한 결과는 [2, 4, 1]입니다.
[3, 6, 1, 5, 2, 4]	{{1, 4, 2}, {2, 5, 3}, {3, 6, 1}}	[1, 5, 4]	각 명령어에 대한 결과는 [1, 5, 4]입니다.

코드 사용법

1. PSG_K번째수 클래스의 solution 메서드에 array와 commands를 전달합니다.
2. 결과로는 각 명령어에 대해 처리된 K번째 수가 포함된 정수 배열이 반환됩니다.

이 문서를 통해 K번째수 문제를 이해하고 해결하는 데 도움이 되기를 바랍니다.