[알고리즘 / 백준] 11004 - K번째 수

 

문제는 위와 같으며 위 문제의 경우 데이터 개수가 최대 5,000,000 개이므로 NlogN 정렬 알고리즘을 통해 겨우 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n, k = map(int, stdin.readline().split())
nums = list(map(int, stdin.readline().split()))

nums.sort()
print(nums[k - 1])

 

병합 정렬을 직접 구현하여 문제를 푸는 경우는 제출할 때 pypy3 로 하면 좀 더 빠르게 계산되기 때문에 시간초과 에러를 해결할 수 있습니다.

from sys import stdin

# 병합 정렬 이용
def merge_sort(array):
    if len(array) == 1:
        return array

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1

    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1

    return array


n, k = map(int, stdin.readline().split())
nums = list(map(int, stdin.readline().split()))

nums = merge_sort(nums)
print(nums[k - 1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(nums);
        System.out.println(nums[nk[1] - 1]);
    }
}