[프로그래머스] 체육복 문제 - Greedy 알고리즘으로 해결하기

 

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

프로그래머스

 

체육복 문제는 탐욕법(Greedy) 알고리즘을 이용하여 해결할 수 있다.

탐욕법은 매 단계에서 최적의 선택을 하여 전체 최적해를 구하는 방법으로, 체육복을 빌려줄 수 있는 조건에 따라 최대한 많은 학생이 체육 수업을 들을 수 있도록 한다.

 

📌 문제 이해하기

 

• 도난당한 학생 중 여벌 체육복이 있는 경우, 빌려줄 수 없음 (본인 체육복만 사용 가능)
• 여벌 체육복을 가진 학생은 자신의 앞번호 또는 뒷번호 학생에게만 빌려줄 수 있음
• 최대한 많은 학생이 체육 수업을 들을 수 있도록 해야 함

 

 

접근 방식

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

- 위에서는 그렇다면 예외처리를 해주는 부분이 필요하다.

1️⃣ set을 활용한 중복 제거

- SET을 사용해서 lost와 reverse 사이의 중복을 제거해주는 방법으로 사용했다.

set_lost = set(lost) - set(reserve)
set_reserve = set(reserve) - set(lost)

set(lost) - set(reserve)를 통해 여벌 체육복이 있지만 도난당한 학생을 제거하여 순수하게 체육복이 필요한 학생들만 남김

 

빌려주는 조건?

- reverse의 각 원자 값의 +1, -1을 진행

2️⃣ 앞번호부터 탐색하며 빌려주기

- 그러나 맨 앞부분부터 체크하는 방식으로, -1 을 먼저 진행해줌

- 번호가 작은 학생부터 차례로 빌려주도록 정렬 후 탐색

for re in sorted(set_reserve):
    if (re - 1) in set_lost:  # 앞번호 학생에게 빌려주기
        set_lost.remove(re - 1)
        answer += 1
    elif (re + 1) in set_lost:  # 뒷번호 학생에게 빌려주기
        set_lost.remove(re + 1)
        answer += 1

 

 

결과 코드

def solution(n, lost, reserve):
    set_lost =  set(lost) - set(reserve)
    set_reserve =  set(reserve) - set(lost)
    answer = n - len(set_lost)
    for re in sorted(set_reserve):
        if (re-1) in set_lost:
            set_lost.remove(re-1)
            answer = answer + 1
            continue
        if (re+1) in set_lost:
            set_lost.remove(re+1)
            answer = answer + 1
    return answer

✅ 시간 복잡도: O(N log N) (정렬 과정 O(N log N) + 탐색 O(N))
✅ 공간 복잡도: O(N)

 

---

 

• 탐욕법(Greedy Algorithm)을 이용해 매 순간 최적의 선택
• set을 활용하여 중복을 제거하고, 도난당한 학생 중 여벌이 있는 경우를 먼저 처리
• 번호가 작은 학생부터 순서대로 탐색하며, 체육복을 빌려줄 수 있는지를 확인
• 앞번호 학생부터 우선적으로 빌려주고, 불가능할 경우 뒷번호 학생에게 빌림