[이코테] 그리디 - 모험가 길드 python

난이도 : ●○○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : 핵심 유형

문제

• 한 마을에 모험가가 N명 있다.
• 모험가 길드에서는 모험가 N명의 공포도를 측정했는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 그룹에 참여해야 여행을 떠날 수 있다.
• 최대 몇 개의 모험가 그룹을 만들 수 있는지 구하라.

 

입력 조건

• 첫째 줄에 모험가의 수 N이 주어진다.(1<=N<=100,000)
• 둘째 줄에 각 모험가의 공포도 값이 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분된다.

출력 조건

• 여행을 떠날 수 있는 그룹 수의 최대값을 출력한다.

 

입력 예시

5
2 3 1 2 2

출력 예시

2

 

아이디어

• 적은 수의 인원으로 많은 그룹을 만들어야 한다.
• 공포도를 오름차순으로 정렬해서 공포도가 낮은 사람들의 그룹부터 결성한다.
• 그룹에 인원을 한명씩 추가하면서, 공포도보다 크거나 같아지면 그룹의 수를 1 증가시킨다.

 

코드

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

cnt = 0
group_cnt = 0

for i in range(n):
    cnt+=1
    if fear[i]<=cnt:
        group_cnt+=1
        cnt=0

print(group_cnt)

 

출처

이것이 취업을 위한 코딩테스트다