💡 문제 해결 아이디어

내가 생각한 아이디어

• *여벌을 가져온 학생이 도난당한 경우는, 일반 학생과 똑같기 때문에, lost와 reserve에서 set을 이용해 모두 제거해 준다.

• 둘다 오름차순으로 정렬.

• cnt = 0, 빌린 학생 수

• index = 0, 여분을 가진 학생의 index

• for 잃어버린 학생 in lost:

  • index가 len(reseve)보다 작고, reserve의 index번째가 잃어버린학생+1 이하인 동안,
    • reserve의 index번째가 잃어버린 학생-1 또는 +1이라면, 빌려줄 수 있으니
      • cnt += 1 빌린 학생수 증가
        • index += 1 빌려줬으니 다음 여분가진 학생으로 넘어가고
        • break 해서 다음 잃어버린 학생으로 넘어간다
    • index += 1 못빌려줘도, 그냥 다음 여분 가진 학생으로 넘어가자

• return ( n - len(lost) + cnt) 전체학생 - 잃어버린 학생수 + 빌린 학생수
  

🛠 피드백

• 시간 단축을 위해 위와 같이 코드를 짜봤는데, 굳이 그러지 않아도 풀 수 있는 문제이다.
• 그냥 lost에 대해서 for문을 돌리면서
  - "in"을 통해서 잃어버린 학생 +1 이나 잃어버린 학생 -1 이 여분 학생 리스트에 있는지 확인하고, 있으면 remove나 del을 이용해서 제거하면 된다.
• 하지만, 다른 문제에서는 list의 in이나 remove, del 등의 시간복잡도가 O(n)이기 때문에 시간 초과로 문제를 풀지 못할 수도 있다. 이점에 유의하자.
  

💻 내가 작성한 코드

def solution(n, lost, reserve):
	# 여벌이 있지만, 도둑맞은 친구는 두 리스트에서 모두 제거.
    lost, reserve = list(set(lost) - set(reserve)), list(set(reserve)- set(lost))
    
    # 두 리스트 모두 오름차순 정렬
    lost.sort()
    reserve.sort()
    
    # 빌린 학생 수
    cnt = 0
    # 여분 있는 학생의 index
    index = 0
    
    for student in lost:
    	# 여분학생의 번호가 (잃어버린 학생 + 1) 이하가 아니라면 
        # 어차피 그 다음 여분학생에게도 못빌리기 때문에 (오름차순 정렬했으니) while문을 돌리지 않는다.
        while index < len(reserve) and reserve[index] <= student+1:
            if abs(reserve[index]-student) == 1:
                index += 1
                cnt += 1
                break
            index += 1
    return (n - len(lost) + cnt)

다른 사람들의 풀이

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _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)