[이것이 코딩 테스트다 with Python] Chapter 11. 그리디 - 모험가 길드

< 모험가 길드 >

 

💬 문제 설명

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상에서 제대로 대처할 능력이 떨어집니다.
....

 

입력	출력
5   2 3 1 2 2	2

💬 입력 조건

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

💬 출력 조건

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

---

✍ 문제요약

N명의 모험가를 대상으로 공포도를 측정했고, 안전한 그룹을 형성 하기 위해서는 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 그룹에 참여 해야한다. 이 경우 최대 몇개의 그룹을 만들 수 있는지 구해야 한다.

 

---

✅  문제 풀이

• 그룹 수를 최대로 하기 위해서는 공포도가 낮은 사람들이 그룹을 먼저 형성해야한다.
• 공포도가 낮은 순으로 정렬을 진행한다.

<오름차순 정렬>

• 순서대로 한명 씩 임시 그룹에 추가하고, 임시 그룹의 인원수가 현재 들어온 모험가의 공포도 보다 크거나 같다면 진짜 그룹을 형성한다.
  

<그룹 형성 과정>

• 임시 그룹의 인원수가 현재 들어온 모험가의 공포도 보다 작다면 그룹을 형성 할 수 없다.

N = int(input())
lst = sorted(list(map(int,input().split())))
total_G = now_G = 0    # 진짜 그룹, 임시 그룹

for level in lst:        
    now_G += 1         # 임시 그룹에 한명 추가
    if now_G >= level: # 임시 그룹의 수가 현재 들어온 사람의 공포도 보다 같거나 크면 
        total_G += 1   # 진짜 그룹이 생성됨
        now_G = 0      # 임시 그룹 초기화

print(total_G)