[Python] 7785 회사에 있는 사람

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

7785번: 회사에 있는 사람

 

문제

 

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

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

코드

 

일단 문제의 조건을 보면 이름의 경우 중복값을 허용하지 않으며, (이름, 퇴근여부)의 형태로 입력을 받고 있다!

그래서 key-value의 쌍 형태를 가지고 있는 딕셔너리를 이용하자고 생각하였음!

딕셔너리의 경우 삽입, 삭제, 조회 명령어 모두 O(1)의 시간 복잡도를 가지며, 이 코드의 경우 이러한 명령어를 for문을 통해 n번 반복하므로 O(N)의 시간복잡도를 가질 것이다!

import sys

n = int(sys.stdin.readline())
d = {}

for _ in range(n):
    name, enter = sys.stdin.readline().rstrip().split()
    
    if enter == 'enter':
        d[name] = 'enter'
    else:
        if d[name]: # 이미 존재하면 삭제
            del d[name]

for i in sorted(d, reverse = True): # 역순 출력
    print(i)