[Python] 7785 :: 회사에 있는 사람

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

7785번: 회사에 있는 사람

 

1트 : 실패(시간초과)

n = int(input())
i = 0
worker = []

while (i < n):
    A, B = map(str, input().split())

    if B == "enter":
        worker.append(A)
    elif B == "leave":
        worker.remove(A)

    i += 1

worker.sort(reverse=True)
length = len(worker)
a = 0

while (a < length):
    print(worker[a])
    a += 1

 

2트 ~ n트 : 내가 알고 있는 모든 방법을 통해 풀려고 노력을 했으나 충격적이게도 전부 시간 초과가 기록되었다 ;;

그래서 직접 찾아보았는데 "리스트 자료구조를 사용하여 풀면 시간 초과가 난다. 리스트가 아닌 딕셔너리 자료구조를 사용하여 풀면 된다." 라는 말을 보게 되었다. 

import sys
input = sys.stdin.readline          #시간초과 해결 꿀팁 

n = int(input())
worker = {}

for i in range(n):
    A, B = map(str, input().split())
    if B == "enter":
        worker[A] = True
    else:
        del worker[A]

namelist = sorted(worker, reverse=True)

for A in namelist:
    print(A)

충격적이게도 그동안 나를 괴롭히던 시간초과를 해결할 수 있었다.

그나마 알고리즘은 맞았는데 이거 좋아해도 되는거 맞나?

 

 

---

참고한 글

https://m.blog.naver.com/crm06217/221832195003

8. 파이썬(Python) 백준 시간초과 해결, 빠른 입력 (import sys), 리스트 함수 시간 복잡도 (Time Complexity)

 

https://lifeofyoori.tistory.com/77

[백준] 7785번: 회사에 있는 사람- 파이썬 (리스트 vs 딕셔너리)