문제
공포도가 X인 모험가는 반드시 X명 이상의 길드원이 필요하다.
예를 들어, 한 모험가의 공포도가 3이면 그 사람은 3명 이상의 길드에 들어간다.
모험가들의 수, 각각의 공포도가 주어질 때, 만들 수 있는 길드의 최대 수를 구하라
(단, 모든 모험가가 길드에 속할 필요는 없다.)
유형 파악
그리디 문제들은 최소한의, 최대한의, 가장 큰, 가장 작은 등의 단어가 들어간다.
이런 단어가 나온다면 항상 그리디는 아니지만 그리디를 먼저 의심하는 습관이 필요하다.
아이디어 및 정당성
만약, 공포도가 2 3 1 2 2이라고 가정하자
이 때, 정렬하면 1 2 2 2 3 이다.
1은 혼자서도 그룹이 가능하다.
2는 둘 이상의 사람이 필요하다,
3은 세명 이상의 사람이 필요하다.
"공포도가 적은 사람일 수록 많은 팀을 만들 수 있다. 또한, 공포도가 높은 사람을 위해 더 많은 사람을 한 그룹에 넣을 필요는 없다."
그룹 : 1
그룹 : 2 2
나머지 : 2 3
나머지를 어떤 그룹에 넣든 만들 수 있는 그룹의 경우의 수중 가장 큰 경우는 2이다.
다른 예시로 2 3 2 3 1 5 4 가 있다고 가정하면
정렬하면 1 2 2 3 3 4 5가 된다.
작은 순서대로 길드를 구성하면
그룹 : 1
그룹 : 2 2
나머지 : 3 3 4 5
나머지를 어떤 그룹에 넣어도 역시나 만들 수 있는 그룹의 경우는 2가 가장 크다.
또 다른 예시로 1 1 1 2 2 2 3 3 일때
그룹 : 1
그룹 : 1
그룹 : 1
그룹 : 2 2
그룹 : 2 3 3
이런식으로 볼 수 있다.
"정리를 하지면 굳이 팀에 공포도가 높은 사람을 끼울 필요는 없고 작은 공포도를 가진 사람순으로 팀을 구성하면 그 값이 만들 수 있는 길드 수 의 최대가 된다."
구현
- 입력을 정렬한다.
- 작은 순서대로 길드를 만든다.
코드
people = list(map(int, input("입력 : ").split()))
people.sort()
count = 0
result = 0
team = []
for i in people:
count = i
team.append(i)
if len(team) == count:
result += 1
team = []
print(result)
공간 복잡도
128MB 제한인데, 굳이 고려할 필요가 없다.
시간 복잡도
사람 수의 최대는 10만명이다. 현재 코드는 모든 사람을 정렬하는 sort()를 사용한다. 시간복잡도는 NlogN이고 for문은 시간복잡도가 N이다. 굳이 따지면 N+NlogN인데 큰 수만 고려하는 빅오표기법으로 O(NlogN)정도 된다. 하지만 5000만번의 파이썬 평균연산에는 충분하다.
