백준 11004번 K번째 수

https://www.acmicpc.net/problem/11004

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

입력 예시 1

5 2
4 1 2 3 5

출력 예시 1

2

---

풀이/접근 방법(JavaScript) ver1.

자바스크립트 내장 sort()함수를 사용해 정렬해줬다.

코드(JavaScript)

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const [N, K] = input[0].split(" ").map(v => Number(v));;
const nums = input[1].split(" ").map(v => Number(v));

nums.sort((a, b)=> a - b);

console.log(nums[K-1]);

풀이/접근 방법(JavaScript) ver2.

처음에 minHeap을 이용한 힙정렬.. 로 풀어보았으나 시간초과로 통과하지 못했다.
vscode에서 테스트케이스 여러개 돌려봤을때는 됐었는데.. ㅠㅠ

내가 짠 로직은 입력받은 숫자들을 배열에 저장해놓고 minHeap으로 정렬해준뒤,
K번만큼 root node에 있는 값을 추출 - 다시 힙정렬 하는 방식이다.
(minHeap은 최상단 root노드 값이 가장 최소값이기 때문에 K번 루트 노드 값을 추출하고 정렬해주면 최종적으로는 오름차순 정렬했을때 K번째 값이 될것이다)

예제처럼 K가 2인 경우는 힙정렬을 2번밖에 하지 않지만, 생각해보니 문제 조건에서 K가 최대 5백만까지 될수 있기 때문에.. 힙정렬로 풀면 당연히 시간초과가 날수밖에 없었다.😭

다음 부턴 입력 조건 잘 보고... 풀자..

코드(JavaScript)

function heapify(arr) {
    const n = arr.length;
    if(n <= 1) return;
    for(let i = Math.floor(n/2)-1; i>=0; i--){
        min_heapify(arr, n, i)
    }
}

function min_heapify(arr, n, i){
    let parent = i;
    let left = i * 2 + 1;
    let right = i * 2 + 2;
    
    if(left < n && arr[left] < arr[parent]){
        parent = left;
    }
    if(right < n && arr[right] < arr[parent]){
        parent = right;
    }
    
    if(i != parent){
        swap(arr, i, parent);
        min_heapify(arr, n, parent);
    }
}

function swap(a, i, j){
    let temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

function _delete(arr){
    swap(arr, 0, arr.length-1);
    const min = arr.pop();
    
    heapify(arr);
    return min;
}

let result = 0;
heapify(nums);
for(let i=0; i<K; i++){
    result = _delete(nums);
}
console.log(result);