[Greedy] 이코테 - 모험가 길드(py)

문제

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라.

 

입력 조건

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

출력 조건

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

입력 예시	출력 예시
5	2
2 3 1 2 2

---

풀이

아이디어

• 일단 공포도를 기준으로 오름차순으로 정렬 수행
• 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인하며, 그룹에 포함될 모험가 수를 계산
• 만약 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 그룹 결성
• => 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성 == 최대한 많은 그룹이 결성되는 방법이므로 항상 최적의 해를 찾을 수 있다.

- 내 풀이

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

groups = 0
info.sort()
min_info = min(info)
while n >= min_info:
    max_info = max(info)
    n -= max_info
    info.remove(max_info)
    groups += 1
    
print(groups)

 

 

책 풀이를 확인하고 나면 말도 안되는 코드..

오름차순으로 정렬은 잘 해줬지만, 이후 list에서 최댓값을 찾아 그 수만큼 먼저 그룹으로 만들어주어 시간이 훨씬 걸린다.

(통과 못하는 테스트 코드도 있을 것 같다)

 

- 답안

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)

 

 

답안을 보고나니 거스름돈 문제를 풀 때 필요한 아이디어와 크게 다르지 않다는 것을 느꼈다.

아직 Greedy 유형 파악이 부족하다.

---

 

출처: 나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.311