2014년 8월 12일 화요일

2075 - N번째 큰수

N크기의 테이블이 주어지면 그 중에서 N번째 큰 수를 구하는 것인데
사실 테이블이라는 형태는 의미 없고 크기가 N2 인 수열에서 N번째 큰 수를 찾으면 된다.

필자는 입력과 동시에 처리하였다. min-heap의 형태를 이용하였는데,
N번째 큰 수를 찾기 위해서는 N개만 누적하고 있으면 되기 때문이다.

12 7 9 15 5 까지 입력된 상황이라면 min-heap은 5 7 9 12 15 의 형태를 이룰 것이다.
다음으로 13 이 들어오면 min-heap에서 최소값을 pop 하고 13 을 push 하면 된다.
그럼 13 이 push된 상황은 7 9 12 13 15 와 같을것이다.

이렇게 N개의 크기를 끝까지 유지하고 입력이 종료 되었을 때 min-heap의 가장 top를 출력하면 그게 N번째 큰 수가 된다.

댓글 없음:

게시글 목록