Priority Queue(:12)를 만들어 보자.
<!> 제출일 : 2006년 9월 28일
문제
Priority Queue는 TOPN 데이터를 가져오기 위한 목적으로 널리 사용된다. Lucene(:12)에서도 TOP score를 가져오기 위한 목적으로 사용하고 있다.
1,000,000 개의 정렬되지 않는 int 형 데이터가 있다. 이 중 가장 큰 값을 가지는 TOPN 개의 데이터를 저장하는 Queue를 유지할 수 있는 알고리즘을 작성해 보자.
언어는 상관 없다.
N은 인자로 받아들인다.
입력 데이터 셋은 난수발생기등을 이용해서 자동 생성시킨다.
데이터셋의 숫자는 중복될 수 있다.
queue의 크기는 N*2를 넘지 않도록 한다.
queue내에 있는 데이터는 완전히 정렬되지 않아도 된다. TOPN개를 포함하고 있음을 보장받을 수 있으면 된다.
문제
- 언어는 상관 없다.
- N은 인자로 받아들인다.
- 입력 데이터 셋은 난수발생기등을 이용해서 자동 생성시킨다.
- 데이터셋의 숫자는 중복될 수 있다.
- queue의 크기는 N*2를 넘지 않도록 한다.
- queue내에 있는 데이터는 완전히 정렬되지 않아도 된다. TOPN개를 포함하고 있음을 보장받을 수 있으면 된다.
예:입력데이터 {100, 5, 8, 2, 12, 9, 3, 90, 1} --> TOP 3 출력데이터 {100,90,12}해답
Recent Posts
Archive Posts
Tags