[이취코테] 모험가 길드

https://youtu.be/2zjoKjt97vQ

이 문제의 해설 영상이다.

문제

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여할 수 있도록 규정했다. 동빈이에게 N명의 모험가에 대한 정보가 주어졌을 때, 만들 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. 
(단, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.)

 

입력 조건: 첫째 줄에 모험가의 수 N이 주어진다. (1 <= N <= 100,000)

                    둘째 줄에 각 모험가의 공포도 값이 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.

 

 

출력 조건: 만들 수 있는 그룹 수의 최댓값을 출력한다.

 

정답 코드

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

result = 0
cnt = 0

for i in data:
    cnt += 1
    if(cnt >= i):
        result += 1
        cnt = 0
print(result)

이 문제는 잘못된 방식으로 접근하여 풀지 못했던 문제라 해설 영상과 코드를 보고 다시 작성한 문제이다.먼저 모든 모험가를 다 포함시키지 않아도 된다는 조건을 읽지 못하고 푸는 실수를 하였기 때문에 가장 공포도가 높은 모험가부터 그룹에 넣는 방식을 선택했다. 하지만 이 경우 답이 나올 수 없었다.

 

풀이 방법은 모든 모험가를 안넣어도 되므로 공포도가 낮은 모험가부터 확인해가며 그룹에 포함될 모험가 수를 계산하는 것이다. 

만약에 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 모험가의 공포도보다 크거나 같다면 그룹을 만들 수 있다. 이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다.따라서 최대한 많은 그룹이 구성되고 항상 최적의 해를 보장한다.

 

배울 점

더 많은 문제를 풀면서 각 문제 풀이에 대한 아이디어를 생각할 수  있는 능력을 길러야겠다.또한 시간이 많이 없어 충분히 고민하지 않고 바로 해답을 봤던 것이 아쉽다. 앞으로는 최대한으로 고민하여 일단 나만의 코드 작성을 완성하는 연습을 해야겠다.

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)