[자료구조/해시] 백준 7785 회사에 있는 사람 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

7785번: 회사에 있는 사람

 

 

 

2. 문제 풀이

 회사에 있는 사람을 역사전순으로 출력하는 문제입니다.

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
company = []
for _ in range(N):
    man, state = input().rstrip().split()
    if state == 'enter':
        company.append(man)
    else:
        company.remove(man)

# 역사전순으로 정렬
company.sort(reverse=True)

# 출력
print("\n".join(company))

 맨 처음에는 리스트를 이용해서 구현했습니다. 하지만 시간초과... 최대 100000개의 로그가 주어지므로, 리스트 구조로는 추가/삭제 작업을 시간 내에 할 수 없습니다.

 

 

 

import sys
input = sys.stdin.readline

# 입력
N = int(input())
company = {}
for _ in range(N):
    man, state = input().rstrip().split()
    if state == 'enter':
        company[man] = True
    else:
        del company[man]

# 출력
print("\n".join(sorted(company.keys(), reverse=True)))

 그대신 딕셔너리(해시맵) 구조를 이용해야 합니다. 딕셔너리 구조는 해시맵을 통해 key-value 값으로 저장되며, 추가 삭제연산이 굉장히 빠릅니다.