문제 01 : 모험가 길드(난이도 : 1/3)

1. 문제 설명

(1) 모험가 길드

• 한 마을에 N명의 모험가가 존재한다.
• 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정한다.
• 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다.
• N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.

(2) 입력 조건

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

(3) 출력 조건

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

---

2. 처음 내가 생각한 풀이

# 모험가들을 공포도가 높은 순서대로 내림차순으로 정렬
people.sort(reverse=1)
groups = 0
# 각 공포도에 대해서
for i in people:
    # 남은 인원 수가 현재 유저의 공포도 보다 크면
    if n - i >= 0:
        groups += 1 # 그룹을 하나 생성
        n -= i # 공포도의 수 만큼 남은 인원 제외
    else:
        break

---

3. 틀린 이유

(1) 문제를 정확하게 이해하지 않음

• 모험가들을 공포도가 높은 순서대로 내림차순으로 정렬할 경우 최댓값을 구할 수 없다.
• 예를 들어, 각 공포도가 [1, 1, 2, 3]인 경우 내림차순으로 정렬해 해당 과정을 진행하면 그룹을 1개밖에 생성하지 못한다.
• 그러나 오름차순으로 정렬하여 진행하면 그룹을 2개 생성할 수 있다.

---

4. 해설 풀이 방법

# 모험가들을 공포도가 낮은 순서대로 오름차순으로 정렬
people.sort()

groups = 0 # 전체 그룹 수
member = 0 # 현재 그룹 인원

# 각 인원들의 공포도에 대해서
for i in people:
    member += 1 # 인원을 한 명씩 모집하여
    if member >= i: # 지금까지 모인 멤버의 수가 공포도 보다 크면 그룹 생성
        groups += 1
        member = 0

---

5. 해설

• 공포도가 낮은 모험가부터 오름차순으로 정렬한다.
• 각 공포도의 단계마다 반복문을 통해 멤버를 추가하는데, 누적된 멤버가 현재 공포도 보다 같거나 높은 경우 그룹을 생성한다.
• 누적된 멤버가 공포도보다 낮다면 그룹은 생성되지 않는다.

---

6. 후기

  처음 코딩 테스트를 준비하면서 풀었던 문제다. 난이도가 제일 낮은 문제임에도 불구하고 처음부터 정답을 맞추지 못하는 기적을 보였다. 너무 쉽게 생각해서 접근한 것도 있고 문제를 꼼꼼하게 읽지 않는 점도 있다. 그리고 한 가지 큰 실수는 문제 유형이 탐욕법인 것을 보고 너무 단순하게 생각해 공포도가 높은 순서대로 정렬한 바보짓도 한 몫했다.

  테스트를 준비한게 작년 10월 중순쯤 부터였는데 지금 생각해보니 너무 설렁설렁 준비한 감이 없지 않아 있다. 포스트 작성일 기준 아마 60문제 가량 공부했는데(이 책은 한 문제당 3번씩 봐서 살펴본 전체 문제수가 적긴 하다.) 물론 처음 보다는 문제 접근 방법이 나아진것 같지만 아직도 스스로가 미흡함을 많이 느끼고 있다. '시작은 미약하나 끝은 창대하리라'라는 성경구절이 생각난다. 아직 창대해지는 과정으로 생각하고 있지만 요즘처럼 설렁설렁 공부하다 보면은 끝도 미약할 수 있다는 불안감이 엄습한다. 좀더 스스로에게 채찍질을 하는 시간이 필요함을 느낀다.

---

github : Algorithms/q1_0.py at main · LeeSeok-Jun/Algorithms (github.com)

LeeSeok-Jun/Algorithms