[Python] 탐욕법(Greedy) : 체육복

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

💡문제💡 

---

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 구하시오.

 

 

[제한사항]

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

[입출력 예]

 

코드 및 풀이💻

---

 

1 ) 각 리스트를 set()을 이용해 중복 제거

2 ) 여벌의 체육복을 가져온 학생 번호 +1 또는 -1가 체육복을 잃어버린 학생 집합에 존재한다면 해당 해당 원소 제거

3 ) 전체 학생 수 - 제거하고 남은 lost_set의 길이 = 체육수업을 들을 수 있는 최대 학생 수