[백준 7785] 파이썬 : 회사에 있는 사람

7785

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

7785번: 회사에 있는 사람

[정답]

import sys
N = int(sys.stdin.readline())
a = {}
for n in range(N):
    name, status = map(str, sys.stdin.readline().split())
    if status == 'enter':
        a[name] = '1'
    elif status == 'leave':
        del a[name]
a = sorted(a.keys(), reverse = True)
for i in a:
    print(i)

.

.

.

[풀이]

간단한 문제 같아 보여 처음엔 리스트를 이용하여 풀었다.

append()와 remove()를 이용하여서.

그런데 시간초과가 떴다.

이유는 remove()의 시간 복잡도가 O(n)이라 

for문을 생각하면 전체 시간 복잡도가 O(n^2)이 된다고 한다.

그래서 시간 초과가 뜨는 거라고 하는데 아직 시간 복잡도는 조금 더 공부해봐야할 것 같다.

 

아무튼 이 문제를 해결하려면 해싱, hashing을 이용하여야 한다고 질문글에서 봤다.

해싱은 무엇인가.

모르겠다.

공부해야할게 또 생겼다.

마침 자료구조와 여러 알고리즘들이 잘 설명되어 있는 블로그를 찾았다. 

한동안은 그 블로그를 보면서 공부할 생각이다.

 

해싱을 몰라도 파이썬에선 간단히 해결할 수 있다.

왜냐하면 파이썬의 딕셔너리가 해시로 구현되어 있기 때문이라고 한다.

따라서 딕셔너리로 del 과 sorted()를 이용해서 풀면 기초 수준의 문제로 난이도가 하락한다.

 

p.s.

장황하게 얘기했는데 요약하자면

1. 시간복잡도를 공부하자

2. 해싱을 공부하자

3. 알고리즘 블로그 공부한다고 ps(problem solving)가 뜸해질 수 있다.