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

deannn.Park·2021년 9월 14일

Weekly Challenge algorithm programmers python

Programmers

목록 보기

21/21

출처ㅣ Programmers 위클리 챌린지

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번은 만났는지 알 수 없습니다.

Solution

내 풀이

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