[그리디 Greedy] 모험가 길드

문제

한 마을에 모험가가 N명이 있고 모험가를 대상으로 공포도를 측정했다.

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다는 규정이 있다.

 

길드장은 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금해한다.

길드장을 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하시오.

단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

 

 

입력 조건

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

 

출력 조건

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

 

입력예시

5

2 3 1 2 2

 

출력 예시

2

 

---

✔ Solution

n = int(input())  # 모험가의 수
travel_X = listmap(int, input().split())  # 각 모험가의 공포도가 들어있는 리스트

X.sort() # 오름차순으로 정렬

travel_cnt = 0   # 현재 그룹에 포함된 모험가의 수
group = 0   # 총 그룹의 수

for i in travel_X:
    travel_cnt += 1
    if travel_cnt >= i :
        group += 1
        travel_cnt = 0  # 그룹이 만들어지면 다시 0으로 리셋
    
print(group)

 

⭐ 문제 포인트

1. 공포도를 받은 리스트 X를 오름차순으로 정렬한다.
2. 모험가의 수를 넣은 변수와 공포도의 값을 비교하여 공포도보다 모험가보다 작거나 같다면 그룹을 만든다.
3. 그룹을 만들면 모험가의 수를 넣은 변수 travel_cnt의 값을 0으로 리셋시켜준다.