입실 퇴실

• 레벨에 비해서는 다소 까다로운 문제. 아이디어도 떠올려야하고, 그 아이디어를 효율적으로 구현할수 있는 방식도 떠올려야 한다
• 단순하게 A와 B만 갖고서 생각하면 A가 B와 만난것을 확신하기 위한 조건은, B보다 일찍 입실하고 늦게 퇴실한 경우에만 가능한 것처럼 보인다. 예를 들어서 A가 B보다 먼저 입실하고 먼저 퇴실했다면, B의 입실보다 A의 퇴실이 더 빨랐을 경우에는 만나지 못한다. 하지만 C가 추가되면, 똑같이 A가 B보다 먼저 입실하고 먼저 퇴실했어도 A와 B가 만난것을 확신할 수 있는 경우가 생긴다. 예를들면 입실시간이 A<B<C이고 퇴실시간이 C<A<B 일 경우에는 A의 퇴실은 B의 입실 이후이므로 A와 B는 만날수밖에 없다.
• 올바른 접근법은, 모든 사람이 가능한 가장 빠르게 퇴실하는 시나리오를 생각하는 것이다. 이렇게 모든 사람이 가능한 최소 시간만큼만 방에 있었을 경우에도 A와 B가 만나는 상황이 생긴다면, 이들은 어떠한 경우에서도 만날 수밖에 없다.
• 따라서 풀이 방법은 모든 사람이 가능한 가장 빠르게 퇴실하는 것을 시뮬레이션하면서 만난 사람들을 카운팅하면 된다.
• 사이트에 올라온 많은 코드들은 이것을 O(n^2)으로 구현했다. 방에 남아있는 사람들의 집합을 유지하면서, 누군가가 방에 들어오면, 방에 있는 모든 사람들에 대해서 카운트를 1씩 올려주는 방식이다. 비효율적이지만 이렇게 해도 통과는 된다.
• 좀더 효율적으로 짜면 O(n)에 구할 수 있다. 모든 사람들에 대해서 입실 시간과 퇴실 시간을 안다고 치자. A와 만나지 못하는 사람은, A가 입실하기 전에 이미 퇴실한 사람, 그리고 A가 퇴실한 이후에 입실한 사람이다. 바꿔 말하면 A와 만나는 사람은, A가 퇴실하기 전에 입실한 사람들 중에서, A가 입실한 이후에 퇴실한 사람이다. {현재까지 입실한 사람의 수}와 {현재까지 퇴실한 사람의 수}를 유지하면서 어떤 사람이 입실할때에는 {현재까지 퇴실한 사람의 수}를 빼고, 퇴실할때에는 {현재까지 입실한 사람의 수}를 더해주면 그 사람이 만난 사람의 수를 구할수 있다.

"""Solution code for "Programmers 86048. 입실 퇴실".

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


def solution(enter, leave):
    people_count = len(enter)
    # met_people_count[X] = {number of people who entered before X left}
    #                       - {number of people who left before X entered}
    met_people_count = [None] * people_count
    leave_count = 0
    for enter_count, person in enumerate(enter):
        met_people_count[person - 1] = -leave_count
        while leave_count < people_count:
            person_to_leave = leave[leave_count]
            if met_people_count[person_to_leave - 1] is None:
                break
            met_people_count[person_to_leave - 1] += enter_count
            leave_count += 1
    return met_people_count