[이코테] greedy : 모험가 길드

문제 정의

• 한 마을에 모험가가 N명 있다.
• 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데, 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
• 모험가 그룹장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는 지 궁금하다.
• N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.

입력 조건

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

출력 조건

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

입출력 예시

# 입력
2 3 1 2 2

#출력
2

로직
1. 최대한 많은 그룹을 만들어야하기 때문에 공포도가 낮은 순으로 정렬한다.
2. 맨 앞에서부터 차례대로 공포도와 그룹에 포함된 모험가 수를 확인하면서 그룹을 확정한다.

내가 짠 코드

prob = list(map(int, input().split())) 
n = len(prob)

# 오름차순 정렬
prob_asc = sorted(prob, reverse=False)

mx = 0 # 그룹 내 최고 공포도
cnt_ppl = 0 # 그룹 내 모험가 수
result = 0 # 그룹 개수

for p in ans: # p : 모험가의 공포도
    cnt_ppl += 1 # 그룹에 모험가 추가
    if p > mx: # 그룹 내 최고 공포도 할당
        mx = p
    if cnt_ppl >= mx: # 그룹 내 최고 공포도가 모험가 수 이상인 경우 그룹 확정 
        result += 1
        cnt_ppl = 0
        mx = 0
print(result)

개선 코드
공포도를 오름차순으로 정렬했기 때문에 그룹 내 최고 공포도는 필요가 없었다.

prob = list(map(int, input().split())) 
n = len(prob)

# 오름차순 정렬
prob_asc = sorted(prob, reverse=False)

cnt_ppl = 0 # 그룹 내 모험가 수
result = 0 # 그룹 개수

for p in ans: # p : 모험가의 공포도
    cnt_ppl += 1 # 그룹에 모험가 1명 추가
    if cnt_ppl >= p: # 현재 공포도가 그룹 내 모험가 수 이상인 경우 그룹 확정 
        result += 1
        cnt_ppl = 0
print(result)