[Programmers] Weekly Challenge 7주차 - 입실 퇴실 (Python)

Weekly Challenge 7주차: 입실 퇴실

문제 설명

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 총 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번은 만났는지 알 수 없습니다.

&nbsp

<span style="color:#48AB7E">Solution</spsn>

내 풀이

def solution(enter, leave):
    N = len(enter)
    meet = [set() for _ in range(N+1)]
    byPerson = [[0, 0] for _ in range(N+1)]

    for i in range(N):
        byPerson[enter[i]][0] = i
        byPerson[leave[i]][1] = i

    for i in range(1, N+1):
        e1, l1 = byPerson[i]
        earlier_leave = leave[:l1]
        for el in earlier_leave:
            e2 = byPerson[el][0]
            l2 = byPerson[el][1]
            if e2 > e1:
                meet[i].add(el)
                meet[el].add(i)
            else:
                for eel in earlier_leave[:l2]:
                    e3 = byPerson[eel][0]
                    if e3 > e2 and e3 > e1:
                        meet[i].add(el)
                        meet[el].add(i)

    return [len(m) for m in meet[1:]]

각 사람별 입실, 퇴실 순서를 만들고(byPerson), 사람들끼리 서로 만났는지 확인을 한다. 각 사람별 만난 사람을 저장할 리스트를 따로 만들어 담는다. 만났는지 확인 방법은 아래와 같다.

두 사람의 입실 순서와 퇴실 순서가 엇갈리는지 확인한다. 엇갈리면 만난것으로 간주.
입실 순서와 퇴실 순서가 엇갈리지 않지만, 전체 명단에서 두 사람보다 일찍 퇴실한 사람들 중에 두 사람보다 늦게 입실한 사람이 존재한다면, 둘은 만난 것으로 간주.
예를 들면, 위의 입출력 예 2번째를 보자. 1번과 4번을 비교하면 입실, 퇴실 순서는 같다. 하지만, 전체 인원 중에서 (1번과 4번 중 일찍 퇴실한) 1번보다 먼저 퇴실한 사람은 2번이 있다. 2번의 입실 순서를 보면 1번, 4번보다 늦게 들어왔다. 즉, 2번은 1번, 4번보다 늦게 들어오고 일찍 나간 것이므로, 1번과 4번은 만났을 수 밖에 없다.

위의 방법을 코드로 만들어 풀었다. 하지만 더 효율적인 방법이 존재했고, 이는 결과 아래를 보면 된다.

결과

Best Code

def solution(enter, leave):
    answer = [0] * len(enter)

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

    return answer

결과를 보면, 이 풀이가 내 풀이보다 더 간단하고 효율도 좋다는 것을 알 수 있다.

방법은 간단하다. 한 명씩 퇴실을 시키며, 퇴실한 당시 방에 있던 인원들을 체크하는 방식이다.

일단 퇴실할 사람방에 들어올 때 까지 한명씩 입실을 한다. (이미 방에 들어와 있다면, 입실할 필요가 없다.)
퇴실할 사람이 방에 들어온다면 해당 사람을 퇴실시킨다.
현재 방에 있는 사람들이 만난 사람 수에 1씩 더해준다.
퇴실한 사람의 만난 사람 수에 현재 방 인원수를 더해준다.