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

- Author: @mildsalmon
- Published: 2021-09-05
- Updated: 2021-09-05
- Source: http://blex.me/@mildsalmon/chap-11-%EA%B7%B8%EB%A6%AC%EB%93%9C-q1-%EB%AA%A8%ED%97%98%EA%B0%80-%EA%B8%B8%EB%93%9C
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 그리디, 풀이, 모험가길드

---

# 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

	```
	
	- 내가 만든 입력 예시

		```

		5
		1 1 1 1 1
		4 4 4 4 4
		1 2 4 3 1
		2 3 1 2 2

		```

- 출력 예시

	```

	2

	```

	- 내가 만든 입력 예시

		```

		5
		1
		2
		2

		```

### B. 내 답안

##### a. 1차 풀이

```python
  
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. 시간 복잡도를 줄인 코드

```python

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. 좀 더 간단하게 푼 코드

```python

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)

```

##### a. 회고

> 풀이

한 그룹에서 가장 공포도가 큰 수만큼 그룹의 인원수를 조정해야한다. 따라서 공포도를 내림차순 정렬하였다. 그리고 모험가 중 가장 큰 공포도만큼 그룹을 짓는 행위를 반복했다.

![](https://static.blex.me/images/content/2021/9/5/10_SDCkPPwuGDSL0susCiuH.jpg)

> 반성

- 너무 복잡하게 생각해서, 상당히 오래 걸린 문제.
- 문제를 그림으로 그리든 해서, 단순화 시키고 간단하게 푸는 연습을 해야겠다.

> 결론

- 책의 정답 코드도 틀릴 수 있다.
	- 내가 만든 테스트 케이스에서는 책의 답지가 정상적으로 작동하지 않는다.
- 일단 문제를 해결하고, 시간 복잡도를 줄여나가는 방법을 찾는 것은 잘한 것 같다.

### C. 책의 문제 해설

공포도를 기준으로 오름차순으로 정렬을 수행하자. 공포도가 가장 낮은 모험가부터 하나씩 확인하여, 그룹에 포함될 모험가의 수를 계산할 수 있다. 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 그룹을 결성할 수 있다.

##### a. 책 답안

[python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/11/1.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년