[코테 스터디] 그리디, 모험가 길드

시작하기에 앞서,

전 학기에 3번의 기회 내에 코딩 테스트를 통과해야 패스를 받을 수 있는 대학 수업을 수강했다. 코딩 테스트를 제대로 준비해 본 적이 없었기에 당연히 야매로 문제를 풀었고 진짜 어거지로 마지막 기회인 3번째에서 겨우 통과했다ㅎㅎ.. 공부를 좀 해야 할 것 같아서 주변 친구에게 제안한 코테 스터디! 고맙게도 그 친구도 마침 스터디원을 구하고 있었다며 각자 사람 1명씩 더 데려옴으로써 총 4명으로 코테 스터디를 진행하게 되었다.

그렇게 약 3개월 동안 스터디를 진행했고, 많은 도움이 됐던 스터디이었기에 복습할 겸 풀었던 문제들을 다시 하나씩 풀이해 보며 회고해 보려고 한다.




사용한 교재는 '이것이 취업을 위한 코딩테스트다 with 파이썬'.
(이것도 그 친구가 추천한 교재인데 여러모로 많이 배우고 고마운 친구 ㅎㅎ)

Q01. 모험가 길드

🐣문제

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

🐥풀이

1. 최대 그룹 수를 구해야하므로 공포도가 작은 모험가부터 그룹 참여
2. 그룹 내에서 공포도가 가장 큰 모험가의 공포도를 그룹 인원으로 구성
3. 모험가 정보를 오름차순으로 정렬하여 1명씩 공포도 및 그룹 구성 체크
4. 최소 인원 조건을 만족한 그룹은 여행 떠남

입력 예제: 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

문제 자체는 쉬웠는데 이걸 글로 설명해낸다는 게 어려웠다. 포스터가 늘어날 때마다 내 글에 전달력도 좋아졌으면 좋겠다 :)