[Python : 나동빈] 모험가 길드

문제

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

• 한 마을에 모험가가 N명
• 모험가별로 가지고 있는 ‘공포도’가 다르다.
• 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여
• 최대 몇 그룹이 탄생하는가

# 입력 예시
5
2 3 1 2 2

# 출력 예시
2

풀이

문제 지문이 애매해서 예시를 보고서야 이해했던 문제
“최저 공포도 X부터 증가시키면서 해당 공포도보다 큰 공포도를 가진 모험가를 묶는다.”
라고 접근하면 풀이가 복잡해진다. 그냥 묶이는 족족 그룹 인원수를 증가시키면 된다.
최대한 작은 공포도부터 그룹에 묶다가
그룹에 속한 인원 수보다 현재 모험가의 공포도가 작거나 같을 때 분리시키면
자연스럽게 최대한 많은 모험가 그룹을 만들 수 있다.

N = input()
X = sorted(list(map(int, input().split())))
total_group = 0
group = 0

for fear in X :
    group += 1
    if fear <= group :
        total_group += 1
        group = 0

print(total_group)

오름차순 정렬을 통한 전처리를 진행해야
반복문 내에서 일일히 공포도를 비교하지 않고도
최대 몇 그룹이 탄생하는지 계산할 수 있다.

대게 이런 류의 문제에서 “그룹이 어떻게 이루어지는지 출력하라.”가 아니고
“몇 그룹이 탄생하는지 출력하라.” 식의 지문이 등장한다면,
리스트(배열) 내의 값을 직접 조작하지 않고도 간단한 풀이가 가능하다.
아마 출제자도 그렇게 풀길 의도하고 문제를 출제하는 것 같다.