[코테 스터디] 그리디, 모험가 길드
시작하기에 앞서,
전 학기에 3번의 기회 내에 코딩 테스트를 통과해야 패스를 받을 수 있는 대학 수업을 수강했다. 코딩 테스트를 제대로 준비해 본 적이 없었기에 당연히 야매로 문제를 풀었고 진짜 어거지로 마지막 기회인 3번째에서 겨우 통과했다ㅎㅎ.. 공부를 좀 해야 할 것 같아서 주변 친구에게 제안한 코테 스터디! 고맙게도 그 친구도 마침 스터디원을 구하고 있었다며 각자 사람 1명씩 더 데려옴으로써 총 4명으로 코테 스터디를 진행하게 되었다.
그렇게 약 3개월 동안 스터디를 진행했고, 많은 도움이 됐던 스터디이었기에 복습할 겸 풀었던 문제들을 다시 하나씩 풀이해 보며 회고해 보려고 한다.
사용한 교재는 '이것이 취업을 위한 코딩테스트다 with 파이썬'.
(이것도 그 친구가 추천한 교재인데 여러모로 많이 배우고 고마운 친구 ㅎㅎ)
Q01. 모험가 길드
🐣문제
공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하여라.
🐥풀이
- 최대 그룹 수를 구해야하므로 공포도가 작은 모험가부터 그룹 참여
- 그룹 내에서 공포도가 가장 큰 모험가의 공포도를 그룹 인원으로 구성
- 모험가 정보를 오름차순으로 정렬하여 1명씩 공포도 및 그룹 구성 체크
- 최소 인원 조건을 만족한 그룹은 여행 떠남
입력 예제: 5 | 2 3 1 2 2
🐓코드
n = int(input())
scare = list(map(int, input().split()))
scare.sort()
result = 0
start, end = 0, scare[0] # 시작점, 그룹 최소 인원
while start+end<=len(scare): # 리스트 넘어가기 전까지
group = scare[start:start+end] # start~start+end 모험가가 같은 그룹
if max(group)>len(group): # 최대 공포도가 인원보다 크면
end = max(group) # 인원 늘리기 (필요한 모험가 수)
else:
start += end # 다음 그룹 시작점 = 현 그룹 시작점+인원
end = scare[start] # 필요한 인원 업데이트
result += 1 # 그룹 여행 떠났으니까 +1
print(result)
⭐2022.03.26
문제 자체는 쉬웠는데 이걸 글로 설명해낸다는 게 어려웠다. 포스터가 늘어날 때마다 내 글에 전달력도 좋아졌으면 좋겠다 :)
Author And Source
이 문제에 관하여([코테 스터디] 그리디, 모험가 길드), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@thguss/코테-스터디-그리디-모험가-길드저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)