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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정하는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. 동빈이는 최대한 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. 동빈이를 위해 N명의 모험가에 대한 정보가 주어질 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하여라.

입력조건

• 첫째 줄에 모험가의 수 N이 주어진다.(1 <= N <= 100,000)
• 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.

출력조건

• 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

사고과정

• 오름차순으로 정렬을 해서 공포도가 최소인 것부터 처리해야 겠다는 사고과정을 풀이와 일치했다.
• 그러나 "공포도 수"와 "그룹의 수"를 동시에 카운트하면서 해주어야 할 것 같은데 이에 대해 명확히 정의가 세워지지 않았다.
• 결국 시간 내 풀지 못하고 풀이를 보았고, 핵심은 "그룹에 포함된 모험가 수 >= 확인하고 있는 공포도 수" 일 때, 그룹을 형성할 수 있다는 것이었음.
• 또 핵심 포인트는 주어진 array = [1, 2, 3, 2, 2] 라고 한다면, 원소의 값(ex. 1,2,3)은 공포도 값을 의미하기도 하지만 원소 자체가 모험가 1명을 의미한다는 것을 캐치했어야 했다.
• 위 2가지 포인트를 풀이에서 문장만 보고 풀이 소스코드는 보지 않고 직접 풀어보자 했는데, 바로 스스로 풀이를 작성할 수 있었다. 확실히 포인트를 캐치하느냐가 정답 당락을 좌우지었다..

풀이(스스로 풀지 못함)

import sys

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

group = 0  # 그룹에 포함되는 모험가 수 세기
count = 0  # 형성되는 그룹 수 세기

for p in phobia:
    group += 1
    if group >= p:
        count += 1
        group = 0

print(count)