[백준 19583번] 싸이버개강총회 - 파이썬

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

19583번: 싸이버개강총회

 

💡문제 분석 요약

개강총회가 시작하기 전에 채팅 기록이 있고, 개강총회가 끝난 후 채팅 기록이 있는 사람의 수를 출력한다.

💡알고리즘 설계

1. 개강총회의 시작시간, 끝난 시간, 스트리밍 종료 시간을 입력받는다.

2. 시와 분으로 입력된 시간을 분 단위로 변환한다.

3. 채팅 시간과 닉네임을 입력받고, 채팅 시간을 분 단위로 변환한다.

4. 채팅 시간이 시작 전일 경우, attend 집합에 추가한다.

5. 채팅 시간이 끝난 후, 스트리밍 종료 전 사이 이고 닉네임이 attend 집합 안에 존재할 경우, count를 1 늘린다. 그 후 참석한 사람이 채팅을 여러번 치는 경우를 방지하기 위해 attend 집합에서 해당 닉네임을 삭제한다.

💡코드

import sys
input = sys.stdin.readline

S, E, Q =map(str, input().split())
S=int(S[3:])+int(S[:2])*60
E=int(E[3:])+int(E[:2])*60
Q=int(Q[3:])+int(Q[:2])*60

attend=set()
count=0

while True:
    try:
        time, name = map(str, input().split())
        time=int(time[3:])+int(time[:2])*60
        if time<=S:
            attend.add(name)
        elif E<=time<=Q and name in attend:
            count+=1
            attend.remove(name)
    except:
        break

print(count)

💡시간복잡도

집합은 Element 추가와 삭제, 특정 Element가 있는지 확인하는데 O(1)이 걸린다.

list나 tuple의 경우, 삭제와 확인이 O(N)이 걸린다.

따라서 전체 코드는 시간 복잡도가 O(N)이다.

딕셔너리도 삭제와 확인이 O(1)이지만, 집합을 이용하는게 더 간단할 것 같아 집합을 이용했다.

💡 느낀점 or 기억할 정보

테스트 케이스나 마지막 케이스를 표시하는 부분이 없으면 try와 except를 이용해 입력을 중단하고 프로그램을 종료할 수 있다.