[백준/Python] 25192 인사성 밝은 곰곰이

[백준/Python] 25192 인사성 밝은 곰곰이

정답 코드 및 설명

N = int(input())

chat_history = set() 
count = 0
for _ in range(N):
    input_chat = input().rstrip()
    if input_chat == "ENTER":
        chat_history.clear()  
    else:
        if input_chat not in chat_history:
            count += 1
            chat_history.add(input_chat)

print(count)

문제를 처음 봤을 때, 닉네임 을 리스트에 적재하고 ENTER 로 새 사람이 들어오게 되면 이모티콘을 반드시 쓰게 되기 때문에 이 점을 이용하기로 했다.

1. ENTER 후 이모티콘을 사용한 사람을 저장
2. 저장하기 전 리스트에 속한 사람이라면 이모티콘을 안쓴다
3. 리스트에 없다면 이모티콘을 쓴다.
4. ENTER 가 또 들어오면 리스트를 초기화 한다.

이 점을 들어 리스트를 사용하여 문제를 풀었다. 하지만 리스트를 사용할 경우 시간 복잡도는 최악의 경우 O(N) 으로 N 의 시간이 걸리기 떄문에 시간 초과로 실패하였다.

때문에 O(1) 의 시간이 걸리는 set 자료 구조로 변경하여 문제를 해결하였다.