[Java]우선순위 큐 응용 - MN개의 조합에서 조건을 만족하는 k번째 수를 찾는 빠르게 찾는 방법 1편

1. 문제 n개의 숫자로 이루어진 수열과 m개의 숫자로 이루어진 수열이 주어졌을 때, 각 수열에서 정확히 원소를 하나씩만 뽑아 나올 수 있는 모든 쌍들을 모두 구하고, 그 값들을 오름차순이 되도록 나열했을 때의 k번째 쌍의 두 수의 합을 구하는 프로그램을 작성해보세요. n,m은 1이상 10만 이하의 자연수 k는 1이상 min(nm, 10만)이하 2. 풀이 가장 쉽게 생각할 수 있는 방법은 mn개의 모든 조합을 만든 다음에 우선순위 큐에 모두 집어 넣고, k번째 빠지는 수를 출력하면 된다 근데 뭐 당연히 시간초과 + 메모리 초과임 m과 n이 10만인데 시간복잡도가 얼마냐 이거 O(M + N + MNlogMN + KlogMN)인가..? 아무튼 O(MN)으로 생각하는 순간 10만*10만 = 100억으로 오바다..