1.모험가 길드

모험가 N명이 있다.
길드에서 N명의 모험가를 대상으로 '공포도'를 측정했다.
공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 한다.
최대 몇 개의 모험가 그룹을 만들 수 있는지 구하시오.

---

입력 조건

• 첫째 줄에 모험가의 수 N이 주어진다. (1 <= N <= 100,000)
• 둘재 줄에 각 모헌가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.

---

출력 조건

• 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

---

입력 예시

5
2 3 1 2 2

---

출력 예시

2

---

# Input
from collections import deque
n = int(input())
array = list(map(int, input().split()))

# Try 1
def func(n, array):
    team = deque()
    result = 0
    max = 0
    for i in range(n):
        if max < array[i]:
            max = array[i]

        team.append(array[i])
        if len(team) >= max:
            team.clear()
            result += 1
            max = 0
    print(result)

func(n, array)

5
2 3 1 2 2
결과값 : 2

다른 입력값과 예상 결과로 풀이에 구멍이 없는지 검사해보았다.

# 입력값
n = 5
array = [1, 1, 1, 1, 1]
# 예상 출력값 : 5
func(n, array)

5

# 입력값
n = 4
array = [5, 5, 5, 5]
# 예상 출력값 : 0
func(n, array)

0

오답 발생

# 입력값
n = 5
array = [1, 2, 2, 3, 1]
# 예상 출력값 : 3
func(n, array)
# 오답 발생 다시 풀자

2

디버깅을 해보니 마지막에 있는 1이 홀로 팀을 이루지 못하여서 였다.
array.sort()를 추가하여 공포도가 작은 사람 순으로 검사를 하게하여 올바른 답을 출력할 수 있게 하였다.

# Try 2
def func(n, array):
    team = deque()
    result = 0
    max = 0
    
    array.sort() # 추가
    
    for i in range(n):
        if max < array[i]:
            max = array[i]

        team.append(array[i])
        if len(team) >= max:
            team.clear()
            result += 1
            max = 0
    print(result)

# 입력값
n = 5
array = [1, 2, 2, 3, 1]
# 예상 출력값 : 3
func(n, array)
# array를 sort하지 않아서 생각과 다르게 동작했다.

3

1회차 풀이 후기

문제는 맞게 잘 푼거 같은데, deque의 사용과 append, clear 연산으로 인해 성능이 저하되었을것 같다.
자료 구조를 사용하지 않고도 풀 수 있는 더 간결한 방법을 잘 생각해보자.