(프로그래머스 연습 문제 풀이) 입실 퇴실

문제 설명
사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.
오늘 회의실에는 총 n명이 입실 후 퇴실했습니다. 편의상 사람들은 1부터 n까지 번호가 하나씩 붙어있으며, 두 번 이상 회의실에 들어온 사람은 없습니다. 이때, 각 사람별로 반드시 만난 사람은 몇 명인지 구하려 합니다.

예를 들어 입실 명부에 기재된 순서가 [1, 3, 2], 퇴실 명부에 기재된 순서가 [1, 2, 3]인 경우,
- 1번과 2번은 만났는지 알 수 없습니다.
- 1번과 3번은 만났는지 알 수 없습니다.
- 2번과 3번은 반드시 만났습니다.

또 다른 예로 입실 순서가 [1, 4, 2, 3], 퇴실 순서가 [2, 1, 3, 4]인 경우,
1번과 2번은 반드시 만났습니다.
1번과 3번은 만났는지 알 수 없습니다.
1번과 4번은 반드시 만났습니다.
2번과 3번은 만났는지 알 수 없습니다.
2번과 4번은 반드시 만났습니다.
3번과 4번은 반드시 만났습니다.

회의실에 입실한 순서가 담긴 정수 배열 enter, 퇴실한 순서가 담긴 정수 배열 leave가 매개변수로 주어질 때, 각 사람별로 반드시 만난 사람은 몇 명인지 번호 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ enter의 길이 ≤ 1,000
1 ≤ enter의 원소 ≤ enter의 길이
- 모든 사람의 번호가 중복없이 하나씩 들어있습니다.
leave의 길이 = enter의 길이
1 ≤ leave의 원소 ≤ leave의 길이
- 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

입출력 예
enter           leave             result
[1,3,2]         [1,2,3]             [0,1,1]
[1,4,2,3]      [2,1,3,4]           [2,2,1,3]
[3,2,1]         [2,1,3]             [1,1,2]
[3,2,1]         [1,3,2]             [2,2,2]
[1,4,2,3]      [2,1,4,3]           [2,2,0,2]

입출력 예 설명
입출력 예 #1
만약, 다음과 같이 회의실에 입실, 퇴실했다면
회의실             설명
[1]               1번 입실
[1, 3]            3번 입실
[3]               1번 퇴실
[2, 3]            2번 입실
[3]               2번 퇴실
[]                3번 퇴실
- 1번과 2번은 만나지 않습니다.
- 1번과 3번은 만납니다.
- 2번과 3번은 만납니다.

만약, 다음과 같이 회의실에 입실, 퇴실했다면
회의실            설명
[1]               1번 입실
[]                 1번 퇴실
[3]               3번 입실
[2, 3]            2번 입실
[3]               2번 퇴실
[]                 3번 퇴실
- 1번과 2번은 만나지 않습니다.
- 1번과 3번은 만나지 않습니다.
- 2번과 3번은 만납니다.
위 방법 외에 다른 순서로 입실, 퇴실 할 경우 1번과 2번이 만나도록 할 수도 있습니다. 하지만 2번과 3번이 만나지 않도록 하는 방법은 없습니다.
따라서
- 1번과 2번은 만났는지 알 수 없습니다.
- 1번과 3번은 만났는지 알 수 없습니다.
- 2번과 3번은 반드시 만났습니다.

입출력 예 #2
문제의 예시와 같습니다.

입출력 예 #3
- 1번과 2번은 만났는지 알 수 없습니다.
- 1번과 3번은 반드시 만났습니다.
- 2번과 3번은 반드시 만났습니다.

입출력 예 #4
- 1번과 2번은 반드시 만났습니다.
- 1번과 3번은 반드시 만났습니다.
- 2번과 3번은 반드시 만났습니다.

입출력 예 #5
- 1번과 2번은 반드시 만났습니다.
- 1번과 3번은 만났는지 알 수 없습니다.
- 1번과 4번은 반드시 만났습니다.
- 2번과 3번은 만났는지 알 수 없습니다.
- 2번과 4번은 반드시 만났습니다.
- 3번과 4번은 만났는지 알 수 없습니다.

def solution(enter, leave):
    answer = [[] for _ in range(len(enter) + 1)]
    meeting = []
    
    # two-pointer
    i, j = 0, 0
    while i < len(enter) or j < len(leave):
        if leave[j] not in meeting:
            answer[enter[i]] = meeting[:] # enter[i]가 회의실에 들어가기 전 기존 사람들
            meeting.append(enter[i])
            i += 1
        else:
            meeting.remove(leave[j])
            j += 1
    for idx, person in enumerate(answer):
        for i in person: # 예) 1번은 [2, 4]와 만났다고 하면 2번, 4번 인덱스에는 1번 정보가 없음
            answer[i].append(idx)
    return [len(set(i)) for i in answer][1:]

투 포인터에 대한 힌트를 얻어 해당 로직으로 풀려고 했던 문제다. meeting이라는 리스트를 새로 만들어 회의실에 들어간 사람을 표시하는 것까진 생각해냈다. 그리고 leave와 meeting을 활용하여 누가 나갔고, 그 사람이 나가기 전까지 몇 명이 회의실에 있었는지를 확인해야 할 필요성을 느꼈다.

다만, answer에 어떻게 답을 저장할지 생각하지 못했는데, n번째 사람이 만난 사람들을 리스트로 표현함으로써 해결했다. 이때 리스트로 표현된 사람들의 경우 n번째 사람을 만났다는 표시를 안했기 때문에 다시 for문을 통해 n번째 사람을 리스트에 넣어주었다.

answer[0]은 0번째이므로 고려하지 않았다. 아래 코드는 위의 과정과 거의 똑같지만 좀 더 간결하게 표현되었다. 누구를 만났는지 리스트로 표현하지 않고 바로 사람 수를 값으로 넣어주었다는 점이 다르다.

# 모범 참고 코드
def solution(enter, leave):
    answer = [0] * len(enter)

    room = []
    idx = 0
    for l in leave:
        while l not in room:
            room.append(enter[idx])
            idx += 1
        room.remove(l)
        for person in room:
            answer[person - 1] += 1
        answer[l - 1] += len(room)

    return answer