[BOJ / 백준] 7785번 회사에 있는 사람 python / 파이썬 집합, 차집합 내림차순 정렬

출처 : https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

---

리스트로 풀었더니 시간초과 나와서

☆집합☆을 이용해서 풀어줬다!!!

 

리스트에서의 x in s 연산의 평균 시간 복잡도 : O(n)
세트에서의 x in s 연산의 평균 시간 복잡도 : O(1)

 

리스트는 어디 있는지 기억 X,
세트와 딕셔너리는 어디 있는지 기억 O(해시 테이블)
검색 시 리스트와 세트, 딕셔너리의 시간복잡도
O(n), O(1), O(1)

# BOJ7785 회사에 있는 사람
import sys
input=sys.stdin.readline

n = int(input())
ans = set()

for i in range(n):
    people, now = input().split()
    if now == "enter":
        ans.add(people)
    elif now == "leave":
        ans.remove(people)

ans = list(ans)
ans.sort(reverse=True)
print(*ans, sep="\n")