체육복
🔗 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42862
😮 알고리즘 풀이 순서
학생들이 가진 체육복을 바탕으로 체육 수업을 들을 수 있는 최대 학생 수를 구하는 문제입니다.
-
학생들이 가진 체육복 정보를 리스트로 변환합니다.
-
체육복을 빌려줄 수 있는 학생을 찾아서 체육복을 빌려줍니다.
- 체육복을 잃어버린 학생이 체육복을 빌려 받을 수 있는 경우는, 앞이나 뒤 학생 중 여분의 체육복을 가진 학생에게 체육복을 빌립니다.
- 체육 수업을 들을 수 있는 최대 학생 수를 구합니다.
여기서 가장 중요한 부분은 2번 부분입니다.
문제를 읽어보면 여분의 체육복이 있는 학생 또한 도난을 당할 수 있습니다. 이때 도란 당하는 체육복은 1개이고, 남은 여분의 체육복으로 해당 학생은 체육 시간에 참여할 수 있습니다. 그러므로 본격적으로 체육복을 빌려주기 전에 여분의 체육복이 있으면서 도난당한 학생들을 처리해줘야 합니다.
그러고 나서 본격적으로 체육복을 도난당한 학생들에게 체육복을 빌려줍니다.
이때 고려해야 하는 부분은 만약 R 번째 학생이 체육복을 가지고 있을 때 이 학생은 R-1 , R+1 번째 학생에게 빌려줄 수 있습니다. 이 때 R-1, R+1 학생 모두 체육복을 가지고 오지 않았을 때 누구에게 빌려줘야 할까요?
그리디 알고리즘은 현재 상황에서 가장 이득이 되는 선택을 해야합니다. 그리고 이 선택은 미래에 영향을 미치거나 번복되서는 안됩니다.
경우의 수는 2가지 인데, 먼저 만약 오른쪽 학생(R+1)에게 우선적으로 빌려준다고 해봅시다. 다음과 같은 상황이 있습니다. 3,5번이 여분의 체육복이 있고 2,4번은 도난 당한 상황입니다. 만약 3번 학생이 오른쪽 학생(4번)에게 빌려주면, 최종적으로 2번 학생은 체육복을 받을 수 없습니다.
하지만 왼쪽 학생(R-1)에게 우선적으로 체육복을 빌려주면 2, 4번 모두 체육복을 빌릴 수 있습니다.
따라서 코드를 작성할 때 주의할 점은 여분의 체육복을 가지고 있는 학생들을 오름 차순으로 확인하면서, 왼쪽과 오른쪽 학생이 도난 당했는 지를 확인하는데, 왼쪽을 먼저 고려합니다. 만약 왼쪽 학생이 도난 당했으면 빌려주고, 그렇지 않으면 오른쪽 학생을 검사해보고 도난 당했으면 오른쪽 학생에게 빌려줍니다.
❤️코드
