백준2075_N번째 큰 수 (java)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

문제 풀이 방식

1. 나의 생각
   • ArrayList에 입력받은 숫자를 모두 넣는다.
   • reverseSort한다.
   • n번째 큰수를 찾는 것이므로 내림차순 정렬된 list에서 n-1번째 숫자를 찾는다.
   • 해당 방법은 시간이 좀 더 오래걸린다.
2. 찾아본 풀이
   • 우선순위큐를 최대힙으로 변경해서 큐에 입력된 숫자를 넣는다.
   • 반복문을 통해 n-1번째까지 큐에서 poll해준다.
   • 반복문이 끝나고 마지막에 한번 poll해주면 n번째 큰수를 출력할 수 있다.

수도코드

int n = input();

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

for(int i=0; i<n*m; i++) {
	pq.add(input());
}

for(int i=0; i<n-1; i++) {
	pq.poll();
}

print(pq.poll());