[python3] 이코테 - 모험가 길드 (ch.11 그리디 - 유형별 기출문제)

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

 

모험가 길드 (ebook기준 p.313)

- 모험가 N명
- 각 모험가 마다 '공포도'를 측정, 공포도가 높은 모험가는 쉽게 공포를 느껴 위험상황 대처능력 저하
- 길드장은 공포도가 x 인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있음
- 최대 몇 개의 모험가 그룹을 만들 수 있는가?
- N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 수의 최댓값을 구하시오.

##### 입력조건
- 첫쨋줄 N 
- 1<= N <= 100,000
- 둘쨋줄, 공포도의 값이 N 이하의 자연수로 주어짐.

 

<문제풀이>

1. 첫번째 시도 (틀린답임)

n = map(int, input())
people = list(map(int, input().split()))

def solution(n,people):
    group = 0
    
    people.sort()
    
    while people: # people에 아무도 없을떄까지 진행
        num_max = people.pop()
        
        if num_max > len(people):
            break
        
        for i in range(0, num_max-1):
            people.pop(0)
        group += 1
    return group

solution(n,people)

바보같이 생각했다. 출력이 원하는대로 나오는줄 알았는데 생각해보니까 '최대'그룹 수라면, '최소'인원으로 최대한 많은 그룹을 결성해야한다. 하지만 이 코드는 '최소'그룹 수를 출력하는 형태로 구현했다. 

2. 두번째 시도 (맞는 답안)

n = map(int, input())
people = list(map(int, input().split()))

def solution(n, people):
    cnt = 0
    group = []
    people.sort()
    
    while people:
        min_num = people.pop(0)
        group.append(min_num)
        if max(group) == len(group):
            cnt += 1
            group = []
            
    return cnt

solution(n,people)

 

<오답노트 (예시답안과 비교)>

예씨답안은 단순한 덧셈과 if문을 활용해서 문제를 풀었다. if문 특성상 조건을 만족하면 count 되는 특성을 잘 생각했어야 했다. 나는 이 과정을 조금 복잡하게 생각한 탓에 while문으로 반복문을 돌렸고, 시간을 조금 잡아먹었던 것 같다.