문제설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
해설
이 문제는 그리디 알고리즘 카테고리에 속해 있다. 따라서 문제해결을 위해서 당장의 해결방법을 생각해 봤을 때, 떠올린 방안은 체육복을 도난당해 체육복이 없는 학생들이 차례로 여벌 체육복을 빌려가는 것이다. 여기서 조건이 있는데, 학생 번호의 앞번호 혹은 뒷번호만 체육복을 빌릴 수 있다.
하지만, 여벌 체육복을 누구한테 빌려주든 체육복을 입을 수 있게 되는 학생 수는 동일할 것이므로 체육복이 없는 학생들이 차례로 앞번호 / 뒷번호에게 체육복을 빌리고, 명단에서 제거하는 식으로 풀이하였다.
또, 우선 여벌 체육복을 가져온 학생이 도난당했을 경우,
- 체육복을 빌려줄 수 없고
- 체육복을 빌릴 필요가 없다.(여벌이 있음)
따라서 reserve와 lost에서 모두 제거해 주는 처리를 먼저 하고, lost의 모든 학생들에 대해 반복하면서 체육복이 없는 사람의 명단만을 남기고 답을 구하였다.
코드
def solution(n, lost, reserve):
answer = 0
# 여벌 체육복이 있는데 도난당한 경우 제외
for r in reserve[:]:
if r in lost:
reserve.remove(r)
lost.remove(r)
for l in lost[:]:
if l-1 in reserve:
reserve.remove(l-1)
lost.remove(l)
elif l+1 in reserve:
reserve.remove(l+1)
lost.remove(l)
answer = n - len(lost)
return answer💡Comment
문제를 풀면서 애먹은 부분이 있는데, 바로 list를 반복하면서 조건에 따라 list의 원소를 제거하는 부분이다. 처음에는 코드를 아래와 같이 작성했다.
for r in reserve:
if r in lost:
reserve.remove(r)
lost.remove(r)이렇게 코드를 작성하면, list를 iterate하면서 조건에 따라 적절하게 제거된 list를 얻을 수 있을것으로 예상했지만, 오류가 발생했다.
찾아본 결과, list를 iterate 하는 과정에서 동일한 list 의 원소를 제거하게 되면 iterate의 기준이 되는 list가 변경되므로 원치않는 결과가 나올 수 있다고 한다. 따라서, 아래와 같이 수정했다.
for r in reverse[:]:
if r in lost:
reserve.remove(r)
lost.remove(r)위의 코드에서는 for문으로 list를 iterate하는 과정에서 reverse[:] 로 list를 복사하여 사용하였다. 이렇게 하면, 기존의 list와 같이 iterate 하면서 기존 list를 변경해도 원하는 결과를 얻을 수 있다.
코딩테스트를 풀면서 많이 접하는 상황인 만큼, 꼭 기억해 두는 것이 좋을 것 같다..!!
📚Reference
