[프로그래머스 위클리 챌린지] 7주차_입실 퇴실

오늘은 13번째로 풀이했다. 더 빨리 풀 수 있었는데 좀 더 효율적인 방법을 고민하다가 조금 더 걸렸다

---

문제 설명

사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다.

오늘 회의실에는 총 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의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

---

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

만약, 다음과 같이 회의실에 입실, 퇴실했다면

• 1번과 2번은 만나지 않습니다.
• 1번과 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)]
    room = []
    ei, li = 0, 0
    while ei<len(enter) or li<len(leave):
        if leave[li] not in room:
            answer[enter[ei]]=room[:]
            room.append(enter[ei])
            ei += 1
        else:
            room.remove(leave[li])
            li += 1
    for p, person in enumerate(answer):
        for met in person:
            answer[met].append(p)
    return [len(set(i)) for i in answer][1:]

이 문제를 투포인터로 접근했다.

 

answer = [[] for _ in range(len(enter)+1)]
room = []
ei, li = 0, 0

answer은 사람 수보다 1 크게 설정하였다. 왜냐하면 사람의 번호가 1번부터 시작하는데 컴퓨터에서 인덱스는 0부터 시작하기 때문에 0번 인덱스를 비워두고 1번부터 시작하기 위해 1 크게 설정한 것이다.

room은 특정 시간에 회의실에 존재하는 사람들을 저장하는 리스트이다.

ei와 li는 각각 enter를 가리키는 포인터와 leave를 가리키는 포인터를 의미한다.

 

while ei<len(enter) or li<len(leave):
    if leave[li] not in room:
        answer[enter[ei]]=room[:]
        room.append(enter[ei])
        ei += 1
    else:
        room.remove(leave[li])
        li += 1

while문의 조건으로 ei와 li가 리스트를 벗어나지 않도록 설정하였다.

2번이 room에서 나가려면 우선 들어와야 한다. 그래서 만약 leave에서 li가 2번을 가리키고 있다면 room에 2번이 들어올 때 까지 사람들을 입장시켜야 한다.

사람이 입장할 때 answer에 현재 room에 있던 인원을 저장한다. 이 인원들은 입장한 사람과 마주칠 사람들이다.

만약 leave에서 li가 가리키는 사람이 room에 존재한다면 그 사람을 room에서 빼낸다.

 

for p, person in enumerate(answer):
    for met in person:
        answer[met].append(p)

이런 과정이 끝나면 answer에는 어떤 사람이 회의실에 입장했을 당시 회의실에 있던 사람들이 저장되어 있다.

예를 들어 2번이 회의실에 들어갔을 때 1번, 4번이 회의실에 있었다면 answer[2] = [1, 4]가 저장되어 있을 것이다.

하지만 1번과 4번은 2번과 만났다는 정보가 저장되어 있지 않기 때문에 answer[1], answer[4]에 각각 2를 추가해야한다.

 

return [len(set(i)) for i in answer][1:]

이 과정이 끝나면 answer에는 각자 마주친 사람의 번호가 저장된 리스트가 저장되어 있고, set()으로 중복을 없앤 후 마주친 사람의 수를 반환하면 된다.

이때, answer의 0번 인덱스를 비워놨으므로 [1:]로 슬라이싱하여 반환하면 답이 된다.

 

 

테스트 결과