자바 코딩테스트 강좌, K번째 수 구하기

문제 설명

주어진 수열에서 특정한 조건을 만족하는 K번째 수를 구하는 알고리즘 문제입니다.
다음과 같은 요구사항을 만족해야 합니다:

수열의 크기 N과 조건을 만족하는 K번째 수를 요청합니다.
수열의 원소는 양의 정수로 구성됩니다.
조건은 두 개의 인덱스 i, j를 사용하여 i번째 수부터 j번째 수까지의 부분 수열을 정렬한 후,
이 부분 수열의 K번째 수를 출력하는 것입니다.

예제 입력

예제 출력

        5
        4
        2

문제 접근 방식

이 문제를 해결하기 위해서는 다음의 단계를 밟아야 합니다:

수열의 크기 N을 입력받습니다.
수열의 원소들을 배열 형태로 입력받습니다.
K번째 수를 구하기 위해 반복문을 통해 여러 조건을 입력받습니다.
각 조건에 대해 부분 수열을 분리하고 정렬 후 K번째 수를 찾습니다.

문제 해결을 위한 자바 코드

        
        import java.util.*;

        public class KthNumber {
            public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                
                // 수열의 크기 N
                int N = sc.nextInt();
                int[] array = new int[N];
                
                // 수열 입력 받기
                for (int i = 0; i < N; i++) {
                    array[i] = sc.nextInt();
                }
                
                // K번째 수를 구할 쿼리 수 Q
                int Q = sc.nextInt();
                
                // 쿼리 처리
                for (int q = 0; q < Q; q++) {
                    int i = sc.nextInt();
                    int j = sc.nextInt();
                    int k = sc.nextInt();
                    
                    // 부분 수열 생성
                    int[] subArray = Arrays.copyOfRange(array, i - 1, j);
                    Arrays.sort(subArray);
                    
                    // K번째 수 출력
                    System.out.println(subArray[k - 1]);
                }
                sc.close();
            }
        }

세부 설명

1. 입력 처리

입력의 첫 번째 줄에서 수열의 크기 N을 입력받고, 다음 N개의 수를 입력받아 배열에 저장합니다.
이 후 K번째 수에 대한 쿼리 수 Q를 입력받습니다.

2. 쿼리 처리

반복문을 통해 각 쿼리에서 i, j, k 값을 입력받고, 해당하는 부분 수열을 만듭니다.
Arrays.copyOfRange() 메소드를 사용하여 수열의 i번째부터 j번째까지의 범위를 잘라내어 새로운 배열 subArray를 생성합니다.

3. 부분 수열 정렬

Arrays.sort() 메소드를 사용하여 생성된 부분 수열을 정렬합니다.
이후 K번째 수는 정렬된 배열의 K-1 인덱스에 해당하는 값을 의미하게 됩니다.

4. 결과 출력

각 쿼리마다 K번째 수를 출력합니다.
이 과정이 반복되어 모든 쿼리가 처리될 때까지 진행됩니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 다음과 같이 분석할 수 있습니다:

수열의 크기 N을 입력받는 과정은 O(N)입니다.
각 쿼리마다 부분 수열을 만드는 데 O(j – i + 1) 시간이 소요됩니다.
부분 수열을 정렬하는 데 O((j – i + 1) log(j – i + 1)) 시간이 필요합니다.
따라서 전체 쿼리를 처리하는 데 평균적으로 O(Q * (j-i+1) log(j-i+1))의 시간 복잡도를 가집니다.

결론

“K번째 수 구하기” 문제는 알고리즘의 기초적인 개념을 익히기에 적합한 문제입니다.
배열과 정렬의 기본적인 사용법을 고찰할 수 있으며, 자바에서 제공하는 라이브러리를 활용하여 효율적으로 문제를 해결할 수 있습니다.
코딩테스트에서 빈번하게 접할 수 있는 문제 유형이라 반드시 연습해두어야 할 것입니다.