[이취코] 알고리즘 유형별 기출문제: 그리디 - 1. 모험가 길드 (Python)

1. 모험가 길드

문제

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

예시

• N=5, 공포도 2 3 1 2 2 → 그룹 1 (1, 2, 3) / 그룹 2 (2, 2) 처럼 2개의 그룹을 만들 수 있음

입출력 조건

• 입력
  • 첫째 줄에 모험가의 수 N이 주어짐 (1 ≤ N ≤ 100,000) O(nlogn) 또는 O(n)
  • 둘째 줄에 각 모험가의 공포도 값이 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분함
• 출력
  • 여행을 떠날 수 있는 그룹 수의 최댓값을 출력

풀이

• 모든 모험가를 넣을 필요가 없다면 공포도가 높은 사람은 두고 가면 되지 않을까? 공포도가 낮은 사람부터 그룹을 짜면 되겠다.
• 정렬 → 맨 앞부터 그룹 만들기
• 현재 인원수가 필요 인원수보다 크거나 같으면 그룹 끝, 현재 인원 수 초기화
• current / require / index
• 시간 복잡도: 정렬 O(nlogn), for loop O(n) → 총 O(nlogn)
• 공간 복잡도: O(n) (크기 n인 배열 하나)

n = int(input())
fears = list(map(int, input().split()))
fears.sort() # 오름차순 정렬
current = require = 1
ans = 0
for fear in fears:
	require = fear
	if require > current:
		current += 1
	else:
		ans += 1
		current = 1
print(ans)

• 개선점
  • require라는 변수가 꼭 필요할까? 맨 마지막에 합류한 모험가의 fear값과 현재 그룹의 인원수를 비교하면 되므로 굳이 require에 담을 필요 없이 fear로 바로 비교하면 된다.
  • current를 계산할 때 1부터 세지 말고 0에서 시작해서 현재 합류하는 시점에서 +1 하는 것이 덜 헷갈릴 수 있다.

n = int(input())
fear = list(map(int, input().split()))
fear.sort() # 오름차순 정렬
ans = crnt = 0
for i in fear:
	crnt += 1
	if crnt >= i:
		ans += 1
		crnt = 0
print(ans)