7785번 회사에 있는 사람(map)

#문제링크 : https://www.acmicpc.net/problem/7785

로그가 주어지고 enter한 회사원은 출근, leave한 회사원은 퇴근한 것으로 최종적으로 남아있는 회사원의 이름을 사전 역순으로 출력하는 문제. 직관적으로 처음 짠 코드는 시간초과가 발생했다. N의 범위가 100만까지라 다시 생각해봐야 한다.

※주의사항

1. 1초의 제한시간임을 고려해, N이 100만까지 반복할 수 있으므로 내부 반복문의 시간복잡도를 잘 생각한다.

1. Code

<2nd try>

vector의 자료구조 특성상 지우고 index를 수정하는 일이 n번 발생한다. 따라서, 첫 번째 코드는 N^2 시간복잡도 그 이상의 복잡도를 가지고, 정렬 역시 한번 더 해주기에 시간초과가 많이 발생한다. map 자료구조는 균형 이진 트리로 insert함수로 삽입시 자동 정렬되어 시간복잡도가 많이 줄어든다.

※주의사항

1. map 개념 이해와 사용법 숙지.

2. Code