質問する

時間制限

1秒

入力

第1列冒険者数N(1<=N<=10000)

の2行目は、各冒険者の恐怖度値N以下の自然数を与え、

をスペースで区切る

出力

ツアー数の最高値

恐怖度Xの冒険者はX人以上の冒険者グループに参加しなければ旅に出られない.最大何人の冒険者グループに会えますか?
例
N=5の場合、各冒険者の恐怖度[2,3,1,2,2]
1組に1、2、3人の冒険者を入れ、2組に残り2人の恐怖度が2の人を入れて、合計2つのグループを作成することができます.

に答える

ソリューション

恐怖度を基準に昇順ソートを行います.(クイックソート条件O(Nlogn)
例)[2,3,1,2]->[1,2,3]
前から恐怖度を逐一確認し、「現在グループ化されている冒険者数」が「現在確認されている恐怖度」以上であればグループ化すればよい.

最後に残りの2人の冒険者はグループを作ることができず、村に残った.
これは恐怖度が昇順に配列されているため,できるだけ多くのグループが生成されることを保証できるからである.

計算時間の複雑さ

リストのソート

リスト数N、クイックソート時O(NlogN)

判断

個のリストを繰り返し、O(N)

従って、総時間複雑度はO(Nlogn)である
N(1<=N<=10000).
50万秒の見込み時間制限1秒通過.

コード#コード#

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data : #공포도를 낮은 것 부터 하나씩 확인하며 
	count += 1 # 현재 그룹에 해당 모험가 확인시키기
	if count >= i : # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
		result += 1 # 총 그룹의 수 증가시키기
		count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result) # 총 그룹의 수 출력