[python] 프로그래머스 - 위클리챌린지 7주차

🤔문제 해결

 

1. 방이 비어있거나 떠날 사람이 없으면 방에 사람을 계속 집어 넣는다.
2. 떠날 사람이 있으면 방안에 있는 사람은 다 마주친 사람들
   1. answer의 인덱스가 사람, 값이 마주친 사람들 집합이다.
   2. 방안에 있는 사람들을 각 인덱스마다 합집합 해준다.
3. 집합의 길이 - 1  이 마주친 사람들 ( 본인 제외 )

 

방을 집합으로 한 이유는 iterable 한 객체 안에 포함 관계를 확인할 때

리스트는 O(N) 이지만, 집합은 O(1) 이므로

마주친 사람들을 집합으로 한 이유는 합집합을 해주면서 중복제거하기 위해

 

💻소스 코드

def solution(enter, leave):
    N = len(enter)
    answer = [set()] * (N + 1)
    room = set()

    e_idx, l_idx = 0, 0
    while l_idx < N:  # 나갈사람 없을 때까지 반복

        if e_idx < N:  # 들어갈 사람 있을 떄
            if not room or leave[l_idx] not in room:  # 비어있거나 나갈사람이 없으면
                room.add(enter[e_idx])
                e_idx += 1

        if leave[l_idx] in room:  # 나갈 사람이 있으면 나가
            for person in room:  # 나갈 때 만난 사람들
                answer[person] = answer[person].union(room)
            room.remove(leave[l_idx])
            l_idx += 1

    return [len(meet) - 1 for meet in answer[1:]]

 

📕문제 확인

출처: 프로그래머스