[알고리즘] 모험가 길드

문제 설명

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.첫째 줄에 모험가의 수 N이 주어지고, 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어진다.

단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 떄문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

 

이때 주어진 입력으로 만들 수 있는 최대한의 그룹 수를 출력하는 프로그램을 작성하시오.

 

 

생각의 흐름

I)아 공포도가 높으면 공포를 쉽게 느끼겠구나.

 

가령 공포도가 100이면 그 사람을 껴줄라면 그 그룹에는 100명의 사람이 필요한 셈이니깐 최대한 공포도가 높은 사람은 마을에 남을 수 있는 방향으로 코드를 짜야겠다.

 

 

II) 그러기 위해서는 입력이 오름차순으로 정렬이 되어야 하니깐 먼저 주워진 입력을 오름차순 정렬을 해줘야겠다

 

III) 이제 정렬된 순서대로 보낼 수 있는 놈들을 보내는 코드를 작성하면 되겠다.

 

 

코드

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

data.sort() #오름차순 정렬

group = 0   #변수 선언
member = 0

for x in data: #1 
    while(True):
        member += 1
        if member == x:
            group += 1
            for _ in range(member):#1
                del data[0]
            member = 0
            break # while문 break
print(group)

 

for문과 while문 부분을 설명하자면 data의 값을 x에 하나씩 넣어준다. group의 값(0)을 1씩 키워가면서 그 값이 data와 일치하면 그때 올커니! 하면서 그 부분까지 그룹으로 묶어준다. 이때 묶어준 그룹으로 여행을 떠나야 (중복이 허용되지 않아야) 하기 떄문에 그 멤버들은 리스트에서 제거가 되어야 한다. 

 

다행히 크기순대로 잘 정렬이 되어있기 때문에 리스트의 원소를 제거하는 del 함수를 사용하면 깔끔하게 해결이 된다.