[이것이 코딩 테스트다] 모험가 길드

<풀이>

일단 리스트를 입력받았을때 정렬을 시켜야 한다 오름차순으로 정렬하면 맨 마지막 값이 가장 큰 값이 나오는데 이 값을 pop 한 후 변수에 저장하고그 값만큼 popleft를 한다(deque를 이용했다) deque 길이가 0이 될때 까지 이  행위를 반복한다.

 

<코드>

from collections import deque as dq
n = int(input())
L = list(map(int,input().split()))
L.sort()
D=dq(L)
result = 0
while len(D) != 0:
    a = L.pop()
    for i in range(a):
        if len(D) == 0:
            break
        D.popleft()
    result += 1
print(result)

 

교재는 다른 방식으로 풀었는데 교재 풀이가 더 나은거 같다 deque도 안쓰기도 하고 시간복잡도가 더 짧다.

 

<교재 풀이>

교재에서는 정렬까지하는건 동일하다 그런데 제일 큰값을 사용하는 것이 아닌 제일 작은 값부터 확인한다(문제에서 모험가는 마을에 그대로 남아 있어도 된다고 적혀 있어서 작은 값으로 해도 문제되지 않는듯) 그 후 그 모험가를 그룹에 넣는다고 가정 한 후에 모험가의 수와 모험가가 가지고 있는 공포도를 비교해서 모험가가 공포도 보다 크거나 같은 순간 그룹을 하나로 묶고 그룹 내 모험가 인원을 초기화 한다

 

 

<교재 코드>

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

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