체육복 - Python

1. 풀이 코드

def solution(n, lost, reserve):
    answer = 0
    student_list = [1 for _ in range(n)]
    
    for lost_index in lost:
        lost_index -= 1
        student_list[lost_index] -= 1
    
    for reserve_index in reserve:
        reserve_index -= 1
        student_list[reserve_index] += 1
    
    if student_list[0] == 2 and student_list[1] == 0:
        student_list[0] = 1
        student_list[1] = 1
        
    for index in range(1, n-1):
        if student_list[index] == 2:
            if student_list[index - 1] == 0:
                student_list[index - 1] = 1
                student_list[index] = 1
            elif student_list[index + 1] == 0:
                student_list[index] = 1
                student_list[index + 1] = 1
    
    if student_list[n - 1] == 2 and student_list[n - 2] == 0:
        student_list[n - 2] = 1
        student_list[n - 1] = 1
    print(student_list)
    
    for item in student_list:
        if item != 0:
            answer += 1
    return answer

 

2. ChatGPT 풀이

이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있습니다. 그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 반복하여 최종 결과를 도출하는 방법입니다. 이 문제에서는 여벌 체육복이 있는 학생이 도난당한 학생들에게 체육복을 빌려주어 최대한 많은 학생이 체육수업을 들을 수 있도록 해야 합니다. 기초부터 차근차근 파이썬으로 푸는 방법을 설명하겠습니다.

1. 문제 분석 및 이해
   학생의 번호는 순차적으로 매겨져 있으며, 여벌 체육복이 있는 학생은 도난당한 학생에게 체육복을 빌려줄 수 있습니다. 다만, 바로 앞번호나 뒤번호의 학생에게만 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번이나 5번 학생에게 체육복을 빌려줄 수 있습니다. 목표는 최대한 많은 학생이 체육 수업에 참여하도록 만드는 것입니다.
2. 알고리즘 접근 방법
   • 우선 여벌의 체육복을 가진 학생이 도난을 당했을 수 있습니다. 따라서 이런 학생의 경우, 체육복을 빌려줄 수 없습니다. 이러한 상황을 먼저 처리해야 합니다.
   • 이후 도난당한 학생에게 체육복을 빌려줄 수 있는 경우를 차례로 찾아 해결합니다.
3. 코딩 단계
   이제 파이썬 코드로 문제를 해결하는 방법을 단계별로 설명해보겠습니다.

Step 1: 기본 코드 구조 만들기

우선 함수의 기본 틀을 잡아보겠습니다.

def solution(n, lost, reserve):
    # 여기에 문제를 해결할 코드를 작성합니다.
    answer = 0
    return answer

 

함수 solution은 세 개의 매개변수를 받습니다:

• n: 전체 학생의 수
• lost: 체육복을 도난당한 학생들의 리스트
• reserve: 여벌의 체육복을 가져온 학생들의 리스트

Step 2: 중복된 학생 처리하기

여벌 체육복이 있는 학생이 도난을 당했을 경우를 먼저 처리해야 합니다. 도난당한 학생 중 여벌 체육복이 있는 학생을 lost와 reserve에서 제거해 줍니다.

def solution(n, lost, reserve):
    # 중복된 학생을 제거합니다.
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    # 위 과정을 통해 중복된 학생이 제거된 lost와 reserve 리스트가 만들어졌습니다.

 

여기서 set을 사용하여 lost와 reserve의 교집합을 제거합니다. 이를 통해 여벌 체육복이 있지만 도난당한 학생을 먼저 처리할 수 있습니다.

Step 3: 체육복 빌려주기

이제 실제로 체육복을 빌려주는 과정을 구현합니다. 여벌 체육복이 있는 학생이 앞뒤 학생에게 체육복을 빌려줄 수 있는지 확인하여 최대한 많은 학생이 체육 수업에 참여할 수 있도록 합니다.

def solution(n, lost, reserve):
    # 중복된 학생을 제거합니다.
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    # 체육복을 빌려주는 과정
    for student in sorted(reserve_set):
        if student - 1 in lost_set:  # 앞 번호 학생에게 빌려줄 수 있는 경우
            lost_set.remove(student - 1)
        elif student + 1 in lost_set:  # 뒷 번호 학생에게 빌려줄 수 있는 경우
            lost_set.remove(student + 1)

    # 최종적으로 체육복을 가지고 있는 학생 수
    answer = n - len(lost_set)
    return answer

Step 4: 코드 설명

• 중복된 학생 제거
  lost_set과 reserve_set을 만들고, 여벌 체육복이 있지만 도난을 당한 학생을 먼저 제거합니다.
• 체육복 빌려주기
  여벌 체육복이 있는 학생을 순회하면서, 그 학생이 앞번호나 뒷번호의 학생에게 체육복을 빌려줄 수 있는지 확인합니다. student - 1이나 student + 1이 lost_set에 있는 경우, 그 학생을 lost_set에서 제거합니다.
• 최종 정답 계산
  체육복이 없는 학생 수를 len(lost_set)으로 계산하고, 이를 전체 학생 수에서 빼서 체육 수업에 참여할 수 있는 학생 수를 구합니다.

전체 코드

이제 모든 과정을 하나로 합친 전체 코드를 다시 보여드리겠습니다.

def solution(n, lost, reserve):
    # 중복된 학생 제거
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

    # 체육복 빌려주기
    for student in sorted(reserve_set):
        if student - 1 in lost_set:
            lost_set.remove(student - 1)
        elif student + 1 in lost_set:
            lost_set.remove(student + 1)

    # 체육 수업에 참여할 수 있는 학생 수 계산
    answer = n - len(lost_set)
    return answer

Step 5: 예제 확인

이제 예제 입력을 통해 코드가 잘 작동하는지 확인해봅시다.

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

 

위 코드는 모든 예제 입력에 대해 올바른 값을 반환합니다.

정리

• 이 문제는 체육복을 도난당한 학생과 여벌 체육복이 있는 학생의 관계를 그리디 알고리즘을 이용해 해결합니다.
• 중복된 학생을 먼저 처리하고, 그 다음에 빌려줄 수 있는 경우를 찾아 최대한 많은 학생이 체육 수업에 참여하도록 합니다.

이렇게 하면, 체육복을 최대한 많은 학생에게 빌려줄 수 있어 문제를 해결할 수 있습니다.

---

• 프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스