merge k sorted arrays

어제 한 스타트업 면접을 봤는데 이 문제가 라이브 코딩 인터뷰 문제로 나왔다.

처음엔 2 sorted arrays를 merge하라고 해서  merge sort 알고리즘에서 merge하듯이 구현했다.

근데 그 다음엔 3개의 sorted arrays를 merge해보라고 해서 혹시 3개만 하면 되는건지

array가 k개로 더 많아질 수 있는건지를 물어봤더니

"어.. 사실 뒤에 문제가 k개를 merge하는 거였어요. 바로 풀어볼래요?"

라고 하셔서 바로 풀어보겠다고 했다. (어차피 3개 array 해봤자 크게 달라질것도 없고 시간낭비일거같아서)

naive하게 풀면  k * k * n일거같다. (k개의 요소중 작은 걸 셀렉하는걸 k*n번 해야되니까. 각 array의 길이는 모두 n이다)

근데 min값 셀렉하는걸 heap일 이용해서 하면 log k로 줄일수있을거같다는 생각이 문득 들어서 라이브로 구현했고

잘 푼거같다.

k * n * log k로 구현 가능