[Java] k번째로 작은 쌍의 합

문제 접근법 이 문제를 처음 봤을때, 풀 수 있는 방법은 쉽게 떠올랐다. 모든 조합을 구해서 pq에 넣는다. pq를 k번만큼 poll하고 결과값을 출력한다. 하지만 중요한 것은 시간 복잡도/공간 복잡도이다. 시간 복잡도 - 모든 조합을 구하여 PQ에 넣는 걸리는 시간: (NM)log(NM) - k번 만큼 poll하는데 걸리는 시간: (KlogNM) 공간 복잡도 - 모든 조합이 우선순위 큐에 들어간다고 가정했을때: O(NM) 문제조건에서 1<=n,m<=100,000으로 주어졌으므로, int형 pq에 모든 조합이 들어간다면 메모리 공간: 10^5 * 10^5 * 4Byte = 40000MB = 40GB 메모리 제한인 80MB를 한참 넘어버린다. 더 공간을 아끼는 방법 다음과 같다. (n)개의 쌍을 pq에 넣어둔다 하나의 쌍을 꺼내어 조건에 맞추어보고, 아니라면 새로 한 쌍을 만들어 pq에 추가한다. 즉, 한번에 N*M개의 쌍을 넣는게 아니라, N개만 넣어두고 메모리 공간을 유지하며 연산...

원문링크 : [Java] k번째로 작은 쌍의 합