일단 이 문제를 풀 때 큰 실수(for loop 안에서 list의 remove 사용 금지)를 했다.
일단 여분의 체육복이 있는데 체육복을 분실한 학생들을 처리해야 한다. 사실상 이 학생들은 체육복을 한 개만 가져온 학생들과 다를 바가 없으므로, lost와 reserve 리스트에서 삭제한다.
remove_list = []
for i in reserve:
if i in lost:
remove_list.append(i)
for i in remove_list:
lost.remove(i)
reserve.remove(i)
그리고 lost 리스트를 오름차순으로 정렬한다. 이 그리디 문제에서 가장 중요한 점은 체육복을 잃어버린 학생들을 탐색하는 순서와 그에 따라 여분의 체육복을 가져온 학생들을 탐색하는 순서이다. 번호를 오름차순으로 탐색할 지, 내림차순으로 탐색할 지, 둘 중에서 확실히 한 쪽을 정해야 한다. 오름차순으로 탐색하면 체육복을 분실한 학생 n이 lost에 있으면 n-1이 reserve에 있는지 확인 후 n+1이 reserve에 있는지 확인해야 한다. 반대로 내림차순으로 탐색하면 체육복을 분실한 학생 n이 lost에 있으면 n+1이 reserve에 있는지 확인 후 n-1이 reserve에 있는지 확인해야 한다.
lost.sort() answer = n
for i in lost:
if i-1 in reserve:
reserve.remove(i-1)
answer += 1
elif i+1 in reserve:
reserve.remove(i+1)
answer += 1
answer -= len(lost)
return answer