Note
Set을 이용한 세션별 고유 사용자 추적 기법을 활용하여 해결하는 문제입니다.
문제
알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.
ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.
새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.
채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!
문제 링크: https://www.acmicpc.net/problem/25192
입력
첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 이 주어진다. ()
두 번째 줄부터 개의 줄에 걸쳐 새로운 사람의 입장을 나타내는 ENTER, 혹은 채팅을 입력한 유저의 닉네임이 문자열로 주어진다. (문자열 길이 )
첫 번째 주어지는 문자열은 무조건 ENTER이다.
출력
채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.
예제
예제 입력 1:
9
ENTER
pjshwa
chansol
chogahui05
lms0806
pichulia
r4pidstart
swoon
tony9402
예제 출력 1:
8
예제 입력 2:
7
ENTER
pjshwa
chansol
chogahui05
ENTER
pjshwa
chansol
예제 출력 2:
5
첫 번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05는 모두 곰곰티콘으로 인사했다.
두 번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다.
예제 입력 3:
3
ENTER
lms0806
lms0806
예제 출력 3:
1
lms0806은 새로운 사람이 들어왔으므로 처음은 곰곰티콘으로 인사하고, 그 뒤로는 일반 채팅을 했다.
문제 분석
이 문제는 Set을 이용한 세션별 고유 사용자 추적 기법을 직접 적용할 수 있는 문제입니다.
핵심 이해
- ENTER: 새로운 사람이 채팅방에 입장 → 새로운 세션 시작
- 각 세션에서: 처음 채팅을 보낸 사용자만 곰곰티콘 사용
- 같은 사용자가 한 세션에서 여러 번 채팅: 첫 번째만 곰곰티콘, 나머지는 일반 채팅
예제 2 상세 분석
ENTER → 세션 1 시작
pjshwa → 세션 1에서 첫 등장 (곰곰티콘) ✓
chansol → 세션 1에서 첫 등장 (곰곰티콘) ✓
chogahui05 → 세션 1에서 첫 등장 (곰곰티콘) ✓
ENTER → 세션 1 종료 (3명), 세션 2 시작
pjshwa → 세션 2에서 첫 등장 (곰곰티콘) ✓
chansol → 세션 2에서 첫 등장 (곰곰티콘) ✓
결과: 3 + 2 = 5
해결 방법
Set을 이용한 세션별 고유 사용자 추적 알고리즘을 사용합니다:
- 현재 세션에서 등장한 사용자들을 Set에 저장합니다.
- ENTER가 나오면 현재 세션의 Set 크기(고유 사용자 수)를 결과에 더하고 Set을 초기화합니다.
- 사용자 이름이 나오면 Set에 없을 때만 추가합니다.
- 마지막 세션의 결과도 결과에 더합니다.
코드 구현
N = int(input())
result = 0
greeting_set = set([])
for i in range(N):
message = input().rstrip()
if message == "ENTER":
# 세션 종료: 현재 세션의 곰곰티콘 사용자 수를 결과에 더함
result += len(greeting_set)
# 새 세션 시작을 위해 Set 초기화
greeting_set = set([])
elif message not in greeting_set:
# 현재 세션에서 처음 등장하는 사용자만 추가
greeting_set.add(message)
# 마지막 세션의 곰곰티콘 사용자 수를 결과에 더함
result += len(greeting_set)
print(result)코드 설명
-
초기화:
result는 총 곰곰티콘 사용 횟수,greeting_set은 현재 세션의 고유 사용자 Set입니다. -
세션 종료 처리 (ENTER):
- 현재 세션의 Set 크기(
len(greeting_set))를 결과에 더합니다. - Set을 비워서 새로운 세션을 시작합니다.
- 현재 세션의 Set 크기(
-
사용자 처리:
message not in greeting_set으로 현재 세션에서 처음 등장하는지 확인합니다.- 처음 등장하는 경우만 Set에 추가합니다 (중복 방지).
-
마지막 세션 처리: 루프 종료 후 마지막 세션의 결과도 더해야 합니다.
예제 1 동작 과정
입력: ENTER, pjshwa, chansol, chogahui05, lms0806, pichulia, r4pidstart, swoon, tony9402
처리:
ENTER → greeting_set = {} (초기화)
pjshwa → greeting_set = {"pjshwa"}
chansol → greeting_set = {"pjshwa", "chansol"}
chogahui05 → greeting_set = {"pjshwa", "chansol", "chogahui05"}
lms0806 → greeting_set = {"pjshwa", "chansol", "chogahui05", "lms0806"}
pichulia → greeting_set = {...} (계속 추가)
r4pidstart → ...
swoon → ...
tony9402 → greeting_set = {8명}
결과: 0 + 8 = 8
예제 3 동작 과정
입력: ENTER, lms0806, lms0806
처리:
ENTER → greeting_set = {} (초기화)
lms0806 → greeting_set = {"lms0806"} (첫 등장, 곰곰티콘)
lms0806 → greeting_set = {"lms0806"} (이미 있음, 일반 채팅)
결과: 0 + 1 = 1
주의사항
Warning
마지막 세션의 결과를 잊지 말고 더해야 합니다. 루프가 끝난 후
result += len(greeting_set)을 한 번 더 실행해야 합니다.
시간 복잡도
- 각 입력 처리: O(1) - Set의
in연산과add연산이 모두 O(1) - 전체 시간 복잡도: O(N) (N은 입력 개수)
Set을 사용하지 않고 리스트로 중복을 체크한다면 O(N²)이 되어 시간 초과가 발생할 수 있습니다.