[백준 27111] 출입 기록 (python)

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

 

처음에는 list로 시도하다, 코드가 비교적 직관적(in, not, add, remove)인 set 함수로 시도하게 되었다. 후에 알게 되었는데, 시간복잡도 관점에서 set 자료구조가 O(1)로 상당한 이점을 보는 것을 알게 되었다.

 

아래 경우를 체크해서 인원을 관리했다.

• 이미 있는 사람이 들어오는 경우
• 없는 사람이 나가는 경우
• 기록이 끝난 후 아직 건물에 남아있는 사람들

 

import sys
input = sys.stdin.readline

n = int(input());
building = set()
cnt = 0

for _ in range(n):
  a, b = map(int, input().split())

  if b == 1:
    if a in building:
      cnt += 1
    building.add(a)
  else:
      if a not in building:
        cnt += 1
      else:
        building.remove(a)

cnt += len(building)
print(cnt)