본문으로 건너뛰기
실습하기

체육복 문제 해설

"체육복 문제"를 탐욕 알고리즘(Greedy Algorithm)을 이용해 해결하는 프로그램을 작성합니다.

학생들에게 체육복을 효율적으로 분배하여 체육수업에 참여할 수 있는 학생 수를 최대화하는 것이 목표입니다.


함수 구현​

  1. 학생 분류:

    • real_reserve는 여분의 체육복을 가진 학생들 중 도난당하지 않은 학생들의 목록입니다.

    • real_lost는 체육복을 잃어버린 학생들 중 여분이 없는 학생들의 목록입니다.

  2. 체육복 분배:

    • 여분의 체육복을 가진 각 학생(real_reserve)에 대해, 바로 앞번호(r - 1)나 뒷번호(r + 1)의 학생이 체육복이 없는 경우(real_lost에 속함), 그 학생에게 체육복을 빌려줍니다.

    • 체육복을 받은 학생은 real_lost 목록에서 제거됩니다.

  3. 결과 반환:

    • 체육복을 받지 못한 학생의 수(len(real_lost))를 전체 학생 수(n)에서 빼서 체육수업에 참여할 수 있는 학생 수를 반환합니다.

모범 답안
def solution(n, lost, reserve):
    # 학생 분류
    real_reserve = [r for r in reserve if r not in lost]
    real_lost = [l for l in lost if l not in reserve]

    # 체육복 분배
    for r in real_reserve:
        if r - 1 in real_lost:
            real_lost.remove(r - 1)
        elif r + 1 in real_lost:
            real_lost.remove(r + 1)

    # 결과 반환
    return n - len(real_lost)

사용 예시​

입출력 예시
print(solution(5, [2, 4], [1, 3, 5]))  # 출력: 5

이 예시에서는 5명의 학생 중 2명이 체육복을 잃어버렸고, 3명이 여분의 체육복을 가지고 있습니다.

여분의 체육복을 가진 학생들이 앞뒤 번호의 학생들에게 체육복을 빌려줄 수 있으므로,

모든 학생이 체육수업에 참여할 수 있게 됩니다. 따라서 함수는 전체 학생 수인 5를 반환합니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!