1. 문제 소개

3433. Count Mentions Per User

2. 나의 풀이

백엔드와 관련된 문제인 것 같다.
힌트를 보지 않고 문제의 조건에 맞게 풀어보았다.
코드가 지저분한데, 다른 풀이를 보고 깔끔하게 푸는 것을 목표로 해야겠다.
시간복잡도는 최악의 경우 $O(m\, log m+ m*n)$이다.

class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        n = numberOfUsers                           # 유저 수
        priority = {"OFFLINE": 0, "MESSAGE": 1}     # 동일 timestamp에서 OFFLINE을 먼저 처리하기 위한 우선순위
        events.sort(key=lambda x: (int(x[1]), priority[x[0]]))  # (시간, 타입우선순위)로 정렬

        online = set(i for i in range(n))           # 현재 online인 유저 집합 (초기에는 모두 online)
        offline = set()                              # 현재 offline인 유저 집합 (추적용)
        cnt = defaultdict(int)                       # cnt[id] = 해당 유저가 마지막으로 OFFLINE된 시각

        ans = [0] * n                                # 유저별 멘션 카운트 결과 배열

        # 정렬된 이벤트를 순차적으로 처리
        for e in events:
            # 현재 이벤트 시각을 기준으로, 60초 이상 지난 OFFLINE 유저들을 online으로 복귀시키는 로직
            for k, v in cnt.items():                 # k: 유저 id, v: 마지막 OFFLINE 시각
                if int(e[1]) - v >= 60:              # 현재시간 - OFFLINE시각 >= 60 이면 복귀 조건 만족
                    online.add(k)                    # online 집합에 추가 (이미 있어도 set이라 안전)
                    if k in offline:                 # offline 집합에 실제로 있으면
                        offline.remove(k)            # offline 집합에서 제거 (없으면 예외 방지)

            # 이벤트 타입에 따라 처리 분기
            if e[0] == "MESSAGE":
                if e[2] == "ALL":
                    # ALL: 모든 유저가 멘션됨 → ans 전체를 +1
                    ans = [x + 1 for x in ans]
                elif e[2] == "HERE":
                    # HERE: 현재 online인 유저만 멘션됨
                    for id in online:
                        ans[id] += 1
                else:
                    # 개별 멘션: "id0 id1 ..." 형태
                    ids = e[2].split(" ")
                    for id in ids:
                        id = int(id[2:])             # "id" 접두사 제거 후 정수 변환
                        ans[id] += 1                 # 해당 유저 멘션 카운트 +1
            else:
                # OFFLINE 이벤트 처리
                id = int(e[2])                       # OFFLINE 대상 유저 id
                online.remove(id)                    # online 집합에서 제거 (현재 online이라고 가정)
                offline.add(id)                      # offline 집합에 추가
                cnt[id] = int(e[1])                  # 마지막 OFFLINE 시각 기록

        return ans                                   # 최종 유저별 멘션 횟수 반환

3. 다른 풀이

훨씬 더 깔끔한 풀이가 나왔다.
최악의 경우 시간복잡도는 같지만 훨씬 빠르게 풀 수 있었다.

class Solution:
    def countMentions(
        self, numberOfUsers: int, events: List[List[str]]
    ) -> List[int]:
        # 이벤트를 (시간 오름차순, 동일 시간에서는 OFFLINE 먼저) 기준으로 정렬
        # e[0] == "MESSAGE" 는 True/False → False(OFFLINE)가 먼저 오도록 함
        events.sort(key=lambda e: (int(e[1]), e[0] == "MESSAGE"))

        count = [0] * numberOfUsers          # 각 유저별 멘션 횟수 결과
        next_online_time = [0] * numberOfUsers
        # next_online_time[i]:
        #   유저 i가 다시 online이 되는 시각
        #   현재 시각 >= next_online_time[i] 이면 online 상태

        # 정렬된 이벤트를 순서대로 처리
        for event in events:
            cur_time = int(event[1])         # 현재 이벤트 시각

            if event[0] == "MESSAGE":
                if event[2] == "ALL":
                    # ALL: 모든 유저가 멘션됨 (online/offline 무관)
                    for i in range(numberOfUsers):
                        count[i] += 1

                elif event[2] == "HERE":
                    # HERE: 현재 online 상태인 유저만 멘션
                    for i, t in enumerate(next_online_time):
                        if t <= cur_time:   # 복귀 시각이 현재 시각 이하 → online
                            count[i] += 1

                else:
                    # 개별 멘션: "idX idY ..." 형태
                    for idx in event[2].split():
                        count[int(idx[2:])] += 1  # "id" 제거 후 해당 유저 카운트 증가

            else:
                # OFFLINE 이벤트 처리
                # 해당 유저는 cur_time + 60 시점까지 offline 상태
                next_online_time[int(event[2])] = cur_time + 60

        return count

4. 마무리

지저분해도 직접 구현하는 것이 더 내 실력에 도움이 된다.
계속 이렇게 진행하자.