[이것이 코딩테스다] 실전-모험가 길드*

나의코드

# 나의 코드
# 그리디 알고리즘
n = int(input())
people = list(map(int, input().split()))
people.sort()

i = -1
count = 0

# 공포도가 큰 사람부터 작은 사람으로 
while i >= -n:
    # 남은 사람이 공포도보다 많은지 파악
    if people[i]-1 <= len(people) + i:
        count +=1
        i -= people[i]
    else:
            i -=1

print(count)

정렬된 리스트가 [1,2,2,2,3]일 때, 3부터 확인한다. 공포도가 3이면 2명의 사람이 더 있으면 그룹을 형성할 수 있다. 그럼 count+=1을 한다. 이제 남은 공포도가 2인 사람을 확인한다. 1명만 더 있으면 그룹 형성이 가능하다. 최종적으로 2그룹이 형성된다. 

이런 식으로 리스트를 정렬한 뒤 가장 큰 수부터 그룹을 형성하는 방법을 사용했다.

 

하지만 이런식으로 하면 그룹 수가 최대가 되지 못한다. 예를 들어 리스트가 [ 1, 2, 2, 2, 5]라 할때 5부터 확인하면 1 그룹 밖에 생성이 안된다. 하지만 1부터 확인한다면, [1], [2,2]로 총 2그룹이 형성된다. 

 

 

정답코드

# 정답 코드
# 그리디 알고리즘
n= int(input())
people = list(map(int, input().split()))
people.sort()

result=0
count=0
for x in people:
    count+=1
    if count >= x:
        result+=1
        count = 0

print(result)

위에서 설명했 듯이 정렬 후 공포가 작은 수 부터 차례대로 확인하여 문제를 해결하였다.

---

그리디 알고리즘의 핵심은 정당성을 찾는 것이다. 내가 단순하게 작은 것부터 또는 큰 것부터 비교하더라도 해당 문제를 풀 수 있을 것이라는 하지만 나는 이러한 정당성을 찾지 않아 위와 같은 오류를 범했다.