오늘의 주제는 탐욕법(Greedy)
문제
입력과 출력
코딩
def solution(n, lost, reserve):
#여벌의 체육복을 가져온 학생이 체육복을 도난당헀을 수도 있음..!!
lost.sort()
reserve.sort()
for i in reserve[:]:
if i in lost:
lost.remove(i)
reserve.remove(i)
#전체 학생 수 n, 도난당한 학생 배열 lost, 여벌 학생 배열 reverse
sum=n-len(lost)
for i in reserve:
if i-1 in lost:
lost.remove(i-1)
sum+=1
elif i+1 in lost:
lost.remove(i+1)
sum+=1
return sum알고리즘
각각의 배열을 먼저 정렬해준다.
reserve의 요소가 lost 배열에도 있다면, 잃어버렸지만 여분이 있는 학생이기 때문에 제거해준다.
그리고 sum이라는 변수에 전체학생수에서 체육복이 없는 학생 수를 뺀 값을 담아주고,
reserve배열, 즉 체육복의 여벌이 있는 사람의 앞번호나 뒷번호가 lost배열(잃어버린 학생 배열)에 있다면 lost에서 지워주고 sum은 +1을 해준다.
회고
오늘도 처음 작성했던 코드부터 시작한다.
이번 문제는 알고리즘 자체를 구성하는 것은 어렵지 않았다...!
이 코드로는 X를 lost에서 찾지 못하는 오류가 났다.
이 코드를 조금씩 수정해나가는 과정!
위와 같이 조건문으로 나눠서 전 오류는 해결했지만, 테스트2는 통과하지 못했다..
근데 나란 사람...
전체 학생수를 n으로 받아서 써야하는데 5로 받고 있었다..ㅎㅎ
그런데,, 이 부분을 해결하고 제출했을 때도 또 통과되지 않는 테스트케이스가 존재했다.
이럴때 해결법>> 분명히.. 내가 문제에서 뭔가를 놓쳤을 것이다!! 문제를 다시 보니 역시 예상한대로 빼먹은 부분이 있었다
여벌의 체육복을 가져온 학생이>> 체육복을 도난 당했을 수도 있는 조건을 생각하지 않았다.
그래서 이 부분을 추가해주고 그 후 코드도 수정해주었는데,,
아직도 의문점이 for i in reserve[:]:에서 [:]없이 실행하면 오류가 나고 이거 하나 추가하면 오류가 안난다..
도대체 왜??!?!?
그래서 지피티에게 물어봤다..
리스트 순회와 제거를 동시에하면 오류가 날 수 있다고 한다
[:] 이 부분은 복사본을 만들어 순회하는 것이며 이러면 원본에서 제거했을 때, 크기 변화와 상관없이 순회 가능!
