codeTree - PriortyQueue [Hard]

https://www.codetree.ai/missions/8/problems/sum-of-kth-smallest-pair?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

 

배운점 : arr1, arr2 배열의 원소들을 정렬해서 미리 배열의 원소들의 합을 구할 때 최소를 구하고자 한다. 이해가 안되었던 로직은 아래와 같다. pq는 두 배열 원소의 합 쌍을 기준으로 오름차순 정렬한 PriorityQueue이다.

 

1. k번째의 최솟값을 구해야 하므로 for 문을 k-1까지 진행하며, pq의 원소를 빼준다. 여기서 중요한 것은 해당 for문 위의 for문 인데, arr2[0]을 임시로 선택 후 arr1의 전체 원소를 pq에 삽입했다. 이때 전체적인 원소의 합 계산없이 이렇게 작성된 로직이 전체 쌍의 최솟값을 구할 수 있을까 의문이 들었다.(사실 이를 해결하는게 문제의 핵심) 일단 의문을 갖고 아래로 넘어가자.

 

2. k번째 인덱스의 최솟값을 구하기 위해 pq에서 차례로 poll을 진행한다. 여기부터가 중요한데, 여기서 해당 원소값의 배열 인덱스가 저장되어있다는 점이다. 현재 arr2[0]을 기준으로 arr1[i]의 원소들이 pq에 들어가 있기에, 확인해보는것이다. arr2[1]가 해당 arr2 배열 사이즈를 넘지 않았는지, 그리고 이에 괜찮다면 원래의 arr1[i]와 다음값인 arr2[1]을 넣어준다.

 

어려울 수 있는데, 필자는 이렇게 생각하기로 했다. 결국 내부적으로 순서를 정해주는 것은 PriorityQueue가 맡았다는 것을.

pq에서 arr1[i]+arr2[i]의 최솟값을 꺼내면서, 해당 인덱스의 다음 요소를 pq에 넣어보고 해당 과정을 반복해서 k-1번까지 진행하는 것이다.

 

해당 문제를 이해하는데, 1시간 가량 걸렸는데 디버깅과 글을 작성하며 코드를 이해할 수 있었다. :)