[파이썬] 프로그래머스 - 위클리 챌린지 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의 길이
  • 모든 사람의 번호가 중복없이 하나씩 들어있습니다.

---

입출력 예

enterleaveresult

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

---

import collections

def solution(enter, leave):
    answer = []
    visit_dict = collections.defaultdict(list)
    
    visit = [0 for _ in range(len(enter)+1)]
    leave_idx = 0
    for i in range(len(enter)):
        visit[enter[i]] = 1
        
        while leave_idx < len(leave) and visit[leave[leave_idx]] == 1:
            tmp = []
            for j in range(1, len(visit)):
                if visit[j] == 1:
                    tmp.append(j)
            
            for j in range(1, len(visit)):
                if visit[j] == 1:
                    visit_dict[j].extend(tmp)     
            
            visit[leave[leave_idx]] = -1
            leave_idx += 1
    
    for i in range(1, len(enter)+1):
        answer.append(len(set(visit_dict[i]))-1)
    
    return answer

 

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.2MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.09ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.3MB)
테스트 6 〉	통과 (0.72ms, 10.3MB)
테스트 7 〉	통과 (0.27ms, 10.3MB)
테스트 8 〉	통과 (1.71ms, 10.6MB)
테스트 9 〉	통과 (2.14ms, 10.9MB)
테스트 10 〉	통과 (73.16ms, 47.3MB)
테스트 11 〉	통과 (547.32ms, 181MB)
테스트 12 〉	통과 (1376.72ms, 387MB)
테스트 13 〉	통과 (0.01ms, 10.3MB)
테스트 14 〉	통과 (0.02ms, 10.3MB)
테스트 15 〉	통과 (0.01ms, 10.3MB)
테스트 16 〉	통과 (0.02ms, 10.3MB)
테스트 17 〉	통과 (0.02ms, 10.3MB)
테스트 18 〉	통과 (0.06ms, 10.3MB)
테스트 19 〉	통과 (0.04ms, 10.3MB)
테스트 20 〉	통과 (0.03ms, 10.3MB)
테스트 21 〉	통과 (4.67ms, 11.9MB)
테스트 22 〉	통과 (2.16ms, 10.7MB)
테스트 23 〉	통과 (0.95ms, 10.3MB)
테스트 24 〉	통과 (749.04ms, 266MB)
테스트 25 〉	통과 (251.50ms, 92.6MB)
테스트 26 〉	통과 (7166.13ms, 1.96GB)
테스트 27 〉	통과 (2895.42ms, 845MB)
테스트 28 〉	통과 (0.04ms, 10.3MB)
테스트 29 〉	통과 (0.09ms, 10.3MB)
테스트 30 〉	통과 (1.66ms, 10.4MB)
테스트 31 〉	통과 (24.97ms, 15.1MB)
테스트 32 〉	통과 (168.22ms, 53.4MB)
테스트 33 〉	통과 (1149.96ms, 310MB)
테스트 34 〉	통과 (1227.78ms, 349MB)
테스트 35 〉	통과 (0.13ms, 10.4MB)
테스트 36 〉	통과 (0.36ms, 10.3MB)
테스트 37 〉	통과 (0.01ms, 10.3MB)

 

후기

 특정 테케에서 시간이 너무 오래 걸린다. 좋지 않은 코드다

 

풀이

 visit을 만들어서 들어가면 1, 나가면 -1을 표시해주도록 했다.

 일단 먼저 들어가게하고, 그 후에 나갈 수 있다면 최대한 나가주도록 한다.(while문)

 나갈 수 있을 때 현재 들어와있는 상태인 모든 인원을 파악하고, 들어와있는 모든 인원 각각씩 현재 있는 상태 모든 인원 명단을 넘긴다.(visit_dict)

 끝에서는 각 인원 별 같이 존재했던 명단(visit_dict)의 list를 set으로 바꿔서 중복을 제거해주었다.