[백준 2075번] N번째 큰 수 - java

문제 설명

1. N x N행렬이 주어진다.

2. 숫자들이 주어진다.

3. N번째에 해당하는 숫자를 구하면 된다.

풀이 과정

 1. 이거 우선순위 큐를 이용해서 풀었는데, 내가 볼 때에는 문제의 조건 중 하나인 '아래 줄이 윗 줄의 숫자보다 크다'를 이용하려면 우선순위 큐를 두 번 사용하는게 좋을 것 같기는 하다.

 2. 그런데 왜인지는 모르겠지만 그걸 쓰지 않고도 해결이 되었다(시간복잡도에서 손해를 많이 보는데도 통과된게 이상한 느낌)

 3. 먼저 우선순위 큐를 사용하면 오름차순으로 정리되는데, 우선순위 큐에 큰 순서대로 N개를 저장해서 갱신해주면 맨 위가 해당 답이 될 것이다.

 4. 그렇다면 총 N개가 N번 들어오기 때문에 처음에 N번 받을 때는 우선순위 큐에 모든 숫자를 받아준다.

 5. 다음부터는 숫자를 받을 때 마다 우선순위 큐의 peek값과 비교하여, 더 큰 숫자면 현재 peek를 poll시키고 새로운 숫자를 받아준다.

 6. 이걸 반복하면 값이 들어올 때 마다 pq가 새로운 peek값을 바꾸어 주고, 마지막까지 모든 값을 받으면 그 때에 peek에 있는 숫자가 답이 된다.

 7. 이렇게 하면 굉장히 쉽게 풀리긴 한다...

코드