[이코테] 모험가 길드

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈)

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

 

문제

• 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.
• 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
• 예를 들어 N=5이고, 각 모험가의  공포도가 다음과 같다고 가정합시다.

2 3 1 2 2

• 이 경우 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있습니다.
• 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

 

문제 조건

• 풀이 시간: 30분
• 시간 제한: 1초
• 메모리 제한: 128MB

 

---

문제를 풀면서 약간 궁금했던 게 1인 그룹은 가능한지 궁금했는데 문제에 명시적으로 주어지지는 않았다

처음에는 그룹이니까 2인 이상이지 않을까 했었는데,

문제를 풀다 보니까 1인그룹도 허용하지 않으면 풀어내기가 굉장히 애매한 문제가 되는 것 같아서

1인그룹도 허용이겠구나 하면서 문제를 풀었다

 

아이디어

 -그룹 내 인원수가 적어야 많은 그룹을 생성할 수 있다

 -공포도 기준 오름차순으로 정렬

 -공포도가 낮은 사람부터 그룹을 맺어준다

 

정당성 (강의 내용)

 -공포도가 오름차순으로 정렬되어 있으면 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다!!

 

작성 코드

N = int(input())

temp = input()
arr=temp.split()
arr.sort()

cnt = 0 #생성 가능한 그룹 수
memNum=0 #현재 그룹 내 인원

for i in arr:
  memNum += 1
  if int(i)<=memNum:
    cnt += 1
    memNum=0
  
print(cnt)

 

파이썬에서 공백 단위로 입력받은 input을 리스트에 int형으로 저장하는 방법

data = list( map(int, input().split()) )

 

파이썬 잘 몰라서 이걸 몰라서.. 입력값 string으로 잘라서 리스트에 저장해놓고 필요할때 형변환해서 썼었다 헿

 

처음부터 int형으로 리스트에 저장하면 아래와 같이 쪼끔 더 깔끔한 코드가 된다

N = int(input())

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

cnt = 0 #생성 가능한 그룹 수
memNum=0 #현재 그룹 내 인원

for i in arr:
  memNum += 1
  if i<=memNum:
    cnt += 1
    memNum=0
  
print(cnt)

 

강의 예시 답안