[이.취.코] Chap 11. 그리드 - Q1. 모험가 길드

@mildsalmon·2021-09-05 10:16

1. 모험가 길드

난이도
- 하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128MB
기출
- 핵심 유형

A. 문제

모험가 N명이 있다.
모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했다.
모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참가해야 여행을 떠날 수 있도록 규정했다.

최대 몇 개의 모험가 그룹을 만들 수 있는가?

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

a. 예를 들면.

N = 5 모험가의 공포도 = 2 3 1 2 2

그룹 1에 공포도가 1, 2, 3인 모험가.
그룹 2에 공포도가 2, 2인 모험가.
총 2개의 그룹을 만들 수 있다.

b. 입력 조건

모험가의 수 N
- 1 <= N <= 100,000
각 모험가의 공포도
- N 이하의 자연수, 각 자연수는 공백으로 구분

c. 출력 조건

여행을 떠날 수 있는 그룹 수의 최댓값

d. 테스트 케이스

입력 예시


5
2 3 1 2 2

내가 만든 입력 예시

출력 예시
```
2
```
- 내가 만든 입력 예시
```
5
1
2
2
```

B. 내 답안

a. 1차 풀이

  
n = int(input())  
arrays = list(map(int, input().split()))   
  
arrays.sort(reverse=True)  
group = 0  
start = 0  
i = 0  
while arrays:  
    if start == i:  
        start = arrays[0]  
        if len(arrays) >= start:  
            group += 1  
            i = 0  
    else:  
        pass  
    arrays.pop(0)  
    i += 1  
print(group)

b. 시간 복잡도를 줄인 코드


n = int(input())  
arrays = list(map(int, input().split()))  
  
arrays.sort(reverse=True)  
group = 0  
start = 0  
count = 0  
ar = []  
del_array = []  
for i in range(len(arrays)):  
    if start == count:  
        start = arrays[i]  
        # ar.append(start)  
        if len(arrays) - len(del_array) >= start:  
            group += 1  
            count = 0  
    del_array.append(arrays[i])  
    count += 1  
  
print(group)

c. 좀 더 간단하게 푼 코드


n = int(input())  
arrays = list(map(int, input().split()))  
  
arrays.sort(reverse=True)  
group = 0  
start = [0]  
count = 0  
ar = []  
del_array = []  
for i in range(len(arrays)):  
    if start[-1] == count:  
        start.append(arrays[i])  
        # ar.append(start)  
        if len(arrays) >= sum(start):  
            group += 1  
            count = 0  
 # del_array.append(arrays[i])  
 count += 1  
  
print(group)