[프로그래머스][Greedy] : 체육복 - Python

🔴 Greedy 알고리즘

• 현재 상황에서 가장 좋은 방향을 선택하는 방법
• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

🟠 문제

 

 

🟡 접근 방법

1. 중복을 허용하지 않은 집합 자료형 Set() 을 활용한다. 
2. Set으로 바꿔주는 이유 ? 첫 단계에서 reserve와 lost에 둘다 존재하는 학생이 있으니 제거하기 위해서
3. 여벌의 체육복을 가져온 학생 reserve도 도난(lost) 당할 수 있기에 정말 빌려줄 수 있는 학생들만을 구하는 set_reserve 를 선언 해준다.
4. 정말 빌려줄 수 있는 set_reserve로 for문을 돌려준다.
5. 앞 번호 학생이 없을 경우 앞 번호 학생에게 빌려주고, 앞이 충족 될 경우 뒷 번호 학생에게 빌려준다.
6. 빌려줬으니 이제 체육복이 생겼다. set_lost 리스트에서 remove함수를 통해 제거 해 준다.
7. 전체 n에서 아직도 set_lost에 남아 있다는 것은 최대한 체육복을 빌려 줬음에도 구할 수 없었음을 의미한다.  이를 전체 학생 수인 n에서 빼면 체육복을 빌릴 수 있던 학생들의 수가 나오고 그게 구하는 정답이 된다.

 

🟢 나름의 해설

set_reserve 를 해 주는 이유 : reserve와 lost에 둘다 존재하는 학생이 있을 수 있으니 빼 준다. 순수하게 빌려줄 수 있는 학생들을 set으로 관리

set_lost 를 해 주는 이유 : 위와 같다. 순수하게 체육복이 필요한 학생만 남게 된다.

 

for문을 통해 한 명씩 꺼내서 i-1 학생이 필요하다면 빌려주게 됐으니, set_lost에서 remove를 통해 빼 준다.

i-1 학생이 필요하지 않으면, i+1학생에게 가서 빌려주고, set_lost에서 remove를 통해 빼 준다.

 

전체 학생 n 에서  set_lost를 빼준다.

빌려갈 수 있는 학생은 for문을 통해 다 빌려줬으니, set_lost에 남은 학생들은 마지막까지 체육복을 못 빌린 학생이 된다.

이를 전체 학생 n에서 빼주면, 참여할 수 있는 학생이 남는다.