체육복

• 아무렇게나 빌릴때 비효율적이 되는 상황은, A는 x와 y에게 빌릴수 있고, B는 y에게만 빌릴수 있는데, A가 x가 아닌 y에게 빌리는 바람에 B가 아무한테도 못빌리는 상황이다. 이런 상황이 생기지 않게 빌려줄 사람을 결정하면 된다.
• 누군가에게 빌려줄 수 있는 사람의 집합이 임의로 주어진다면, 이분 매칭을 통해서 풀어야 하는 문제지만, 지금처럼 번호가 1만큼 차이나는 사람에게만 빌려줄수 있다는 규칙이 있다면 그리디로 쉽게 풀수 있다. 여분 체육복이 있는 사람들중 번호가 작은 사람 순서대로 체육복을 빌려주기 시작하는데, 체육복을 빌려줄수 있는 사람중 가장 번호가 작은 사람에게 체육복을 빌려주면 된다.
  • 다만 이 문제에서는 추가 규칙으로 여벌 체육복이 있는 사람이 자기의 체육복을 도난당했으면, 자기가 여벌 체육복을 입어야 한다는 규칙이 있다. 따라서 빌려줄 우선 순위는 {나}, {나의 앞번호}, {나의 뒷번호} 순서이다.
• 처음에 정렬에 O(nlogn)이 걸린다. 그 뒤에는, 각 학생에 대해서 누구한테 빌려줄지 결정하는 것은 O(1)이다. 모든 학생에 대해서 빌려줄 사람을 결정하는 것은 O(n). 총 시간 복잡도는 O(nlogn)

"""Solution code for "Programmers 42862. 체육복".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42862
- Solution link: http://www.teferi.net/ps/problems/programmers/42862
"""


def solution(n, lost, reserve):
    answer = n - len(lost)
    lost_set = set(lost)
    for r in sorted(reserve):
        for l in (r, r - 1, r + 1):
            if l in lost_set:
                lost_set.remove(r)
                answer += 1
                break

    return answer