문제

• 시간제한
  • 1초
• 입력
  • 첫째줄에 모험가 수 N (1<=N<=100,000)
  • 둘째줄에 각 모험가의 공포도값을 N이하의 자연수로 주어지며, 공백으로 구분
• 출력
  • 여행을 떠날 수 있는 그룹수의 최댓값

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있음. 최대 몇개의 모험가 그룹을 만날 수 있는가?

예시
N=5일때, 각 모험가의 공포도는 [2,3,1,2,2]
그룹1에 공포도 1,2,3인 모험가 한명씩 넣고, 그룹2에 공포도가 2인 남은 두명을 넣으면 총 2개의 그룹을 만들 수 있음.

풀이

풀이 아이디어

공포도 기준으로 오름차순 정렬을 수행하자. (퀵정렬 기준 O(NlogN))
예시) [2,3,1,2,2] -> [1,2,2,2,3]

앞에서터 공포도를 하나씩 확인하며, '현재 그룹에 포험된 모험가 수'가 '현재 확인하고 있는 공포도'보다 크거나 같다면, 이를 그룹으로 설정하면 된다.

마지막 남은 2명의 모험가는 그룹을 만들지 못하고, 그대로 마을에 남아있는다.

이는 공포도가 오름차순으로 정렬되어있다는 점에서, 최대한 많은 그룹 생성의 최적을 보장한다.

시간복잡도 계산

• 리스트 정렬
  • 리스트 갯수 N이므로, 퀵정렬시 O(NlogN)
• 판단
  • 리스트 갯수 만큼 반복하므로 O(N)

그러므로, 총 시간복잡도는 O(NlogN)
N (1<=N<=100,000) 이므로
500,000초 예상. 시간제한 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) # 총 그룹의 수 출력