이것이 코딩 테스트이다 - 모험가 길드

모험가 길드 문제는 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다.

첫째줄에 n이 주어지고 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어집니다.

모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.

<나의 풀이>

from collections import deque

if __name__ == '__main__':
    n = int(input())
    list1 = list(map(int, input().split()))
    list1.sort(reverse=True)
    arr = deque(list1)
    result = 0

    while arr:
        x = arr[0]

        if x <= len(arr):
            for i in range(x):
                arr.popleft()
        else:
            break
        result += 1

    print(result)

나의 풀이는 잘못 되었습니다. 해당 알고리즘은 그리디가 적용되어야 됩니다. 하지만 저는 가장 공포도가 높은 모험가를

먼저 파티에 넣는 식으로 하였기 때문에 그룹의 수는 가작 적은 그룹의 수가 리턴 될 것입니다. 그것을 알고도 위와같은 알고리즘을 사용한 것은 가장 큰 값을 기준으로 해야 나중에 뒤에서 더 큰 공포를 가진 모험가가 나타나서 위 조건을 이탈하는 케이스를 생각했기 때문입니다.

아래는 정답입니다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

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

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
	count += 1
    if count >= i:
    	result += 1
        count = 0

 

정답을 보면 if count >= i:

라는 조건이 있습니다. 해당 조건 덕분에 뒤에서 갑자기 공포도가 큰 모험가가 포함 되어도 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날수 있는 조건을 만족할 수 있습니다.