[이코테] 그리디 - 모험가 길드 with 파이썬

1. 문제

• 공포도가 높을수록 공포를 많이 느끼는 사람이다.
• X 공포도를 가진 사람은 X 명 이상의 그룹에 속해야 그룹을 형성할 수 있다.
• 모험을 떠날 수 있는 최대 그룹수를 구하라 ( 단, 모든 사람이 그룹이 결성이 되지 않아도 된다. )

입력 조건

• N 명 , 전체 인원 수
• 모험가의 공포도 간격을 두고 N 개수 만큼 들어온다.
  

출력 조건

• 모험을 떠날 수 있는 최대 그룹수를 구하라.

입력 예시

5
2 2 1 2 3

출력 예시

2

2. 아이디어

• 최대 그룹수를 구하라고 했다. 그러려면, 최소한의 인원으로 그룹을 구성해야 한다.
• 공포도가 낮은 사람부터 최소한의 인원수로 그룹을 형성해 나가야 그룹수가 많아진다.
• 사람을 오름차순으로 정렬하고, 문제에서 그룹이 형성가능한 최소 조건대로 공포도가 인원수보다 작거나 같다면 그룹을 만든다.

3. 예제코드

# 입력
N = int(input())
people = list(map(int, input().split()))

# 길드원 공포도 오름차순 정렬
people.sort()

# 결과값 및 인원수 측정 객체 초기화
result = 0    # 그룹수
count = 0     # 그룹의 인원수

# 메인
for panic in people:
    count += 1 # 그룹인원 추가
    if count >= panic: # 인원의 공포도가 그룹의 인원수보다 적으면,
        result += 1    # 그룹을 형성한다. 
        count = 0      # 인원수를 다시 초기화 한다. 
        
print(result)

어려웠던 점

• 문제부터 이해가 안됬었다. 공포도 x 이상인 사람은 x 명 이상인 그룹에 참여 해야한다.. 뭔소리지? 이랬다.
• 인원수를 올리고, 그룹을 형성하고, 인원수를 초기화 하는 과정을 생각해내는 것도 구현하는 것도 어려웠다.

참고

• 이것이 취업을 위한 코딩테스트다.
• 우노님 블로그 : https://wooono.tistory.com/539