[프로그래머스] 오픈채팅방

문제 요약

오픈채팅방의 기록에는 다음 세 가지 명령이 들어 있다.

Enter uid nickname
Leave uid
Change uid nickname

입장과 퇴장은 관리자 메시지를 남긴다.

[닉네임]님이 들어왔습니다.
[닉네임]님이 나갔습니다.

닉네임이 변경되면 과거에 출력된 메시지의 닉네임도 모두 최신 닉네임으로 바뀐다.

모든 기록을 처리한 뒤 관리자에게 보여 줄 최종 메시지 배열을 반환해야 한다.

핵심 아이디어

메시지의 순서와 닉네임 정보는 분리해서 관리한다.

각 사용자 ID의 최신 닉네임을 딕셔너리에 저장한다.

nickname_by_uid = {}

입장과 퇴장 기록은 나중에 메시지를 만들 수 있도록 명령 종류와 사용자 ID만 저장한다.

events = []

모든 기록을 한 번 읽은 뒤에는 각 ID의 최종 닉네임을 알 수 있다.

그다음 입장과 퇴장 이벤트를 순서대로 확인하며 최신 닉네임을 붙여 메시지를 만든다.

닉네임 변경 기록은 이벤트를 만들지 않는다.

Enter: 닉네임 갱신 + 입장 이벤트 추가
Leave: 퇴장 이벤트 추가
Change: 닉네임 갱신만 수행

왜 두 번 순회하는가

과거 메시지의 닉네임도 현재 닉네임으로 바뀌어야 한다.

예를 들어 다음 기록을 생각해보자.

Enter uid1234 Muzi
Leave uid1234
Enter uid1234 Prodo

첫 번째 입장 메시지는 처음에는 Muzi로 보이지만, 모든 기록이 처리된 뒤에는 Prodo로 보여야 한다.

따라서 입장 메시지를 읽는 즉시 문자열로 완성하면 이전 메시지를 다시 수정해야 한다.

대신 첫 번째 순회에서는 사용자 ID와 이벤트만 저장한다.

("Enter", "uid1234")
("Leave", "uid1234")
("Enter", "uid1234")

최종 닉네임이 확정된 뒤 두 번째 순회에서 메시지를 만들면 모든 메시지에 최신 닉네임을 자연스럽게 적용할 수 있다.

명령어 처리

각 기록은 공백으로 나누어 처리한다.

parts = record.split()
command = parts[0]
uid = parts[1]

Enter

입장 명령은 사용자 ID의 닉네임을 갱신하고 입장 이벤트를 저장한다.

nickname = parts[2]
nickname_by_uid[uid] = nickname
events.append(("Enter", uid))

같은 사용자가 나갔다가 새 닉네임으로 다시 입장한 경우에도 최신 닉네임으로 갱신된다.

Leave

퇴장 명령은 닉네임을 바꾸지 않는다.

퇴장 이벤트만 저장한다.

events.append(("Leave", uid))

Change

닉네임 변경 명령은 관리자 메시지를 남기지 않는다.

사용자 ID의 최신 닉네임만 변경한다.

nickname = parts[2]
nickname_by_uid[uid] = nickname

메시지 만들기

모든 기록을 읽은 뒤 이벤트를 순서대로 확인한다.

for command, uid in events:
    nickname = nickname_by_uid[uid]

명령이 Enter면 입장 메시지를, Leave면 퇴장 메시지를 추가한다.

if command == "Enter":
    answer.append(f"{nickname}님이 들어왔습니다.")
else:
    answer.append(f"{nickname}님이 나갔습니다.")

풀이 과정

1. 사용자 ID별 최신 닉네임을 저장할 딕셔너리를 만든다.
2. 입장과 퇴장 기록만 저장할 이벤트 배열을 만든다.
3. 모든 기록을 순회하며 Enter와 Change에서 닉네임을 갱신한다.
4. Enter와 Leave는 이벤트 배열에 저장한다.
5. 이벤트 배열을 다시 순회하며 최종 닉네임으로 메시지를 만든다.

Python 코드

def solution(record):
    nickname_by_uid = {}
    events = []

    # 첫 번째 순회: 최신 닉네임과 이벤트 순서를 저장한다.
    for log in record:
        parts = log.split()
        command = parts[0]
        uid = parts[1]

        if command == "Enter":
            nickname_by_uid[uid] = parts[2]
            events.append((command, uid))

        elif command == "Leave":
            events.append((command, uid))

        else:
            # Change는 메시지를 남기지 않고 닉네임만 변경한다.
            nickname_by_uid[uid] = parts[2]

    answer = []

    # 두 번째 순회: 최종 닉네임으로 메시지를 만든다.
    for command, uid in events:
        nickname = nickname_by_uid[uid]

        if command == "Enter":
            answer.append(f"{nickname}님이 들어왔습니다.")
        else:
            answer.append(f"{nickname}님이 나갔습니다.")

    return answer

코드 설명

nickname_by_uid

nickname_by_uid = {}

사용자 ID를 키로, 최신 닉네임을 값으로 저장한다.

닉네임은 중복될 수 있지만 사용자 ID는 고유하므로 ID를 기준으로 관리해야 한다.

events

events = []

관리자 메시지가 출력되는 순서를 보관한다.

닉네임 변경은 메시지를 출력하지 않으므로 events에 저장하지 않는다.

최신 닉네임 갱신

nickname_by_uid[uid] = parts[2]

Enter와 Change 모두 사용자 닉네임을 최신값으로 바꾼다.

이렇게 하면 과거 이벤트를 메시지로 만들 때도 마지막으로 변경된 닉네임을 사용할 수 있다.

이벤트 순서 유지

events.append((command, uid))

입장과 퇴장이 발생한 원래 순서를 저장한다.

두 번째 순회에서 이 순서를 그대로 사용하므로 출력 메시지의 순서가 보장된다.

예시

다음 입력을 살펴보자.

record = [
    "Enter uid1234 Muzi",
    "Enter uid4567 Prodo",
    "Leave uid1234",
    "Enter uid1234 Prodo",
    "Change uid4567 Ryan",
]

모든 기록을 처리한 뒤 사용자 ID별 최신 닉네임은 다음과 같다.

uid1234: Prodo
uid4567: Ryan

입장과 퇴장 이벤트는 다음 순서로 남아 있다.

Enter uid1234
Enter uid4567
Leave uid1234
Enter uid1234

최종 결과는 다음과 같다.

[
    "Prodo님이 들어왔습니다.",
    "Ryan님이 들어왔습니다.",
    "Prodo님이 나갔습니다.",
    "Prodo님이 들어왔습니다.",
]

시간 복잡도

기록의 개수를 N이라고 하자.

첫 번째 순회와 이벤트를 처리하는 두 번째 순회를 수행한다.

O(N)

딕셔너리 조회와 삽입은 평균적으로 O(1)에 동작한다.

공간 복잡도

사용자 ID별 닉네임과 입장 및 퇴장 이벤트를 저장한다.

O(N)

정리

이 문제는 메시지 순서와 닉네임 정보를 분리해 관리하는 구현 문제다.

사용자 ID별 최신 닉네임 저장
입장과 퇴장 이벤트만 순서대로 저장
Change는 닉네임만 갱신
모든 기록 처리 후 이벤트에 최종 닉네임 적용

과거 메시지의 닉네임까지 함께 바뀐다는 조건 때문에, 메시지를 즉시 완성하지 않고 두 번 순회하는 것이 핵심이다.