[LV.3] 탐욕법(Greedy) > 체육복

# 탐욕법이란? 매 순간 가장 좋아 보이는 선택을 하는 알고리즘 전략

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

---

문제 설명

• 어떤 학생들은 체육복을 도난당했고, 어떤 학생들은 여벌의 체육복을 가지고 있는 상황
• 도난 당한 학생은 앞번호 또는 뒷번호 학생에게만 체육복을 빌릴 수 있음
• 여벌이 있지만 도난당한 학생은 빌려줄 수 없음 (자기 것만 있음)
• 목표: 최대한 많은 학생이 체육수업을 들을 수 있도록 체육복을 빌려주는 방법을 찾아 참여 가능한 학생 수를 반환
• 제한사항
  전체 학생의 수는 2명 이상 30명 이하
  체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없음
  여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없음

---

풀이 흐름

1. 도난도 당하고, 여벌도 있는 학생 → 이 학생은 빌려줄 수 없으므로 제거

2. 여벌 체육복이 있는 학생이 도난당한 학생에게 빌려주기

3. 전체 학생  수 - 여전히 체육복 없는 학생 수 = 수업 참여 가능한 학생 수

---

정답 코드

def solution(n, lost, reserve):

    # 도난도 당하고 여벌도 있는 학생은 제외 (자기 것만 있음)
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    # 여벌 있는 학생이 앞 번호 → 뒷 번호 순서로 체육복 빌려주기
    for r in sorted(reserve_set):
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)

    # 수업 들을 수 있는 학생 수 = 전체 - 아직도 체육복 없는 사람 수
    return n - len(lost_set)

---

sorted()로 작은 번호부터 처리하는 이유?

• 작은 번호부터 체육복을 빌려주면, 빌려줄 학생들이 겹치지 않고 순서대로 처리 가능
• 반대로 큰 번호부터 하면 중간 번호 학생이 빌리지 못할 수도 있어 최대 참여 인원이 줄어들 가능성 존재
• 그래서 앞 번호부터 차례대로 처리하는 것이 체육복 분배를 효율적이고 안정적