[그리디] 모험가길드 (파이썬)

문제

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 한다.

최대 몇개의 모험가 그룹을 만들 수 있을까?

입력조건

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

출력조건

1. 여행을 떠날 수 있는 그룹 수의 최댓값 출력

 

입력예시

5

2 3 1 2 2

 

출력예시

2

---

 

import sys

N = int(input())

input_lists = list(map(int,sys.stdin.readline().split()))

input_lists.sort()

group = 0
N = N-1

while N>0:    
    max = input_lists[N]
    N = N -max
    group +=1

print(group)

 

문제 해설

for문을 활용한다면 O(N)의 시간이 소요된다. 그래서 리스트 전체를 돌지만 max(그룹에 포함된 인원 수)만큼 뛰어넘으면

최대 O(N)의 시간으로 단축시킬 수 있다.