제한 사항에 문제에 대한 핵심을 들어있다.
- 여벌의 체육복을 가져온 학생과 체육복을 도난 당한 학생중에 중복된 번호가 없다.
중복되는 경우가 없으므로 reserve = [1, 1, 2], lost = [3, 3, 4] 같은 경우가 불가능하다.
- 여별의 체육복을 가져온 학생이 체육복을 도난 당했을 수 있다. 이때 체육복은 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄수 없다.
여별의 체육복이 있는 학생도 도난 당할 수 있다는 것은 lost와 reserve에 공통적으로 값이 존재할 수 있다는 것이다.(lsot = [2,3] reserve = [2, 4])
여별의 체육복은 1개 밖에 없다고 가정하므로 2는 3에게 체육복을 빌려 줄수 없다. 그러므로 lost와 reserve에 같은 값을 제외 시켜주어야 한다.따라서 중복을 제거하고 두 집합 속 공통적인 값을 제거하기 위해 set 함수를 이용해 차집합 값을 구한다.
def solution(n, lost, reserve):
_lost = set(lost) - set(reserve)
_reserve = set(reserve) - set(lost)
for i in _lost:
if i-1 in _reserve:
_reserve.remove(i-1)
elif i+1 in _reserve:
_reserve.remove(i+1)
else:
n-=1
return n
주의할 점은
i+1부터 체크하게 되면 testcase 17, 18, 19, 20, 25에서 실패하게 된다.
예시를 들면_lost = [2,4], _reserve = [1,3]
_lost에서 2를 꺼내 2+1 _reserve 에 있는지 확인한다. 있으므로 빌려 주고 더 이상 빌려 줄수 없으므로 _reserve에서 3일 제거한다.다시 반복문을 통해 _lost에서 4을 꺼내 _reserve에서 4+1, 4-1에 빌려 줄수 있는 학생이 있나 확인하나 3번은 아까 빌려 주었으므로 빌릴 수 없어 최종적으로 4를 반환하게 된다. 5명의 학생이 빌릴 수 있음에도 최적의 해를 얻을 수 없게 된다.
2는 1, 3번 학생에 모두 받을 수 있으나 4는 3번 학생에게만 받을 수 있기 때문에 이러한 문제가 발생한다.
def solution(n, lost, reserve):
_reserve = [r for r in reserve if r not in lost]
_reserve = sorted(_reserve)
_lost = [l for l in lost if l not in reserve]
for r in _reserve:
f = r - 1
b = r + 1
if f in _lost:
_lost.remove(f)
elif b in _lost:
_lost.remove(b)
return n - len(_lost)
이 코드 같은경우
2023/02/21일 기준
reserve리스트를 정렬해주지 않으면 testcase를 일부 통과하지 못하는데 아마 정렬되어있지 않은 testcase가 일부 추가된 것 같다.