[백준 python] 백준 7785번 회사에 있는 사람

 

문제

 

• 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
• 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
• 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

 

 

 

입력

 

• 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
• 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

 

 

 

출력

 

• 현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

 

 

 

 

 

나의 답

 

n = int(input())
count = []


for i in range(n):
    name, existence =input().split()

    if(existence == "enter"):
        count.append(name)
    
    if(existence == "leave"):
        count.remove(name)

count = sorted(count, reverse=True)

for j in count:
    print(j)

 

 

 

결국 enter한 뒤, leave가 나와야지만 제외되는 것이니 leave를 중점적으로 생각하고 name을 list에 담으면 된다고 생각했다

따라서 , enter 이 나오면 count 리스트에 추가해주고 leave가 나오면 count 리스트에 name을 이용하여 remove 하였다

 

 

그런데 remove를 사용한다는 것 자체가 딕셔너리를 사용할 때보다 순회를 더 많이 해야되서 시간복잡도 자체가 높다고 한다

이 문제는 딕셔너리를 이용해 푸는 것도 괜찮으니 그렇게 풀어도 괜찮을 듯 싶다.

 

까먹고 있던 시간복잡도 등을 다시 알아봐야겠다

 

 

 

다른 사람의 답

 

import sys

n = int(sys.stdin.readline())
temp = dict()

for _ in range(n):
    a, b = map(str, sys.stdin.readline().split())

    if b == "enter":
        temp[a] = b
    else:
        del temp[a]

temp = sorted(temp.keys(), reverse=True)

for i in temp:
    print(i)