[이코테] 모험가 길드

이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다.

 

 

 

 

📋 문제

한 마을에 모험가가 N명 있습니다.

모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

 

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

동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다.

 

예를 들어 5명의 모험가가 모였고 이들의 공포도는 2, 3, 1, 2, 2와 같다고 가정하자.

이때 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있다.

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

 

동빈이를 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

 

 

👉 입력

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

 

 

👈 출력

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

 

 

📝 풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

group, count = 0, 0
for fear in arr:
  count += 1
  if count >= fear:
    group += 1
    count = 0

print(group)

 

n과 arr에 입력을 받는다.

n은 모험가의 수, arr은 각 모험가의 공포도를 저장한다.

 

최대 그룹 수를 구하기 위해 먼저 arr을 오름차순으로 정렬한다.

공포도가 높을 수록 하나의 그룹에 많은 사람을 넣어야 하기 때문에 모든 사람이 그룹에 속할 필요가 없다면 공포도가 높은 사람을 배제시키는 편이 그룹 수를 많이 만들 수 있다.

 

따라서 공포도가 적은 사람부터 그룹을 결성한다.

group은 만들어진 그룹의 수를 저장하고 count는 한 그룹 당 사람의 수를 저장한다.

for문 안에서 count를 하나씩 늘리며 공포도와 현재 그룹에 들어있는 사람 수를 비교한다.

공포도와 사람 수가 같으면 그룹이 결성될 수 있으므로 group을 1 늘리고 count를 다시 0으로 초기화한다.

 

 

🔍 참조

이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 나동빈)