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

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

 

문제설명

위 문제는 들어온 사람과 나온 사람을 체크하는 단순한 문제이다.
단순하게 LIST에 추가하여 LEAVE가 나오면 제외하는 방식으로 풀어도 되지만

입력의 숫자가 10^6으로 많다는 것을 고려해야한다.
만약 모든 입력이 enter인 경우에 1+2+...+10^6-1번의 연산이 필요하다.
즉, 리스트로 구현하는 경우 시간 제한에 걸리게 된다.

탐색시간을 줄일 수 있는 방법인 set이나 dictionary를 통해 구현하면 탐색 시간은 항상 1 데이터의 갯수를 10^6으로 가정했을 때 충분히 시간 내에 구할 수 있다.

 

풀이

n = int(input())

names = dict()

for i in range(n):
    data = input().split()

    if data[1] == 'enter':
        names[data[0]] = 0
    elif data[1] == 'leave':
        names.pop(data[0], None)

temp = list(names.keys())

for i in sorted(temp, reverse=True):
    print(i)

먼저 dictionary를 선언한다. 기본 dictionary의 경우 최초값이 들어올 때 초기화를 해줘야하기 때문에 
enter를 입력받으면 안에 값을 0으로 초기화했다. (key - value를 생성하는 작업)
그리고 leave가 들어오면 해당 key에 대한 값을 삭제한다.

위 방법처럼 진행하면 들어와서 나가지 않은 이름에 대한 것만 key가 생성되어
마지막에 key들만 정렬하여 출력하면 된다.

기본 dictionary 문제라서 어렵지 않을 수 있지만 dictionary의 기본 개념과 최초 key를 생성할 때는 초기화해줘야한다는
개념을 알고가면 좋을 것 같다.