[필수 문제] k번째 큰 수 찾기

1. 문제

N개의 자연수가 주어질 때, 이 자연수들 중에서 k번째로 큰 수를 찾는 프로그램을 작성하시오. 만약 k=1 이라면, 가장 큰 수를 찾으면 된다.

---

입력

첫 번째 줄에 자연수 N, k가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ k ≤ 10) 두 번째 줄에 N개의 자연수가 주어진다. 

출력

첫 번째 줄에 k번째 수를 출력한다.

예제 입력

10 3
1 5 2 3 8 4 7 3 2 10

예제 출력

7

 

 

 

2. 풀이

이 문제는 시간 복잡도를 고려하여 풀어야한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // Arrays.sort(arr);
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < n-1; j++) {
                if(arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }

        bw.write(arr[n-k] + "");
        br.close();
        bw.flush();
        bw.close();
    }

}

만약 다음과 같이 풀이할 경우, O(n^2)의 시간이 소요된다. 즉, 주어진 N의 범위를 생각한다면 10,000,000,000 번의 시간이 소요된다. 따라서 k번 만큼의 루프를 돌아 시간복잡도를 생각하여 풀어야한다는 점이 이 문제의 가장 중요한 요점이다.

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n-1; j++) {
        if(arr[j] > arr[j+1]) {
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}