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

[22] 오픈 채팅방

책 구매하기

문제 정보

• 분류: 해시
• 정답률: 57%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: uid 매핑, 문자열 처리, 최종 닉네임, 로그 재구성
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42888

문제를 읽을 때 체크할 포인트

핵심은 메시지를 바로 확정하지 않는 것이다. 먼저 uid별 최종 닉네임을 다 만든 뒤, 기록 중 Enter와 Leave만 다시 읽어서 문장을 만들면 된다.

배열을 처음부터 끝까지 비교하는 쪽으로 가면 코드는 길어지고 예외도 많아진다. 이 문제는 필요한 정보를 키-값으로 압축하는 순간 풀이가 짧아진다.

풀이 흐름

1. 기록 전체를 읽으며 uid → 최종 닉네임 매핑을 만든다.
2. Enter와 Leave 기록만 남겨 순서를 보존한다.
3. 남겨 둔 기록을 다시 순회하면서 최종 닉네임으로 메시지를 만든다.

구현할 때 놓치기 쉬운 부분

입장, 퇴장, 닉네임 변경 로그를 읽는 순서와 실제로 출력할 닉네임을 적용하는 시점을 구분해야 한다. 로그를 읽는 순간 문자열을 확정해버리면 나중에 바뀐 닉네임이 앞선 기록에 반영되지 않는다.

파이썬 정답 코드

def solution(record):
  # 기록 전체를 읽으며 uid → 최종 닉네임 매핑을 만든다.
  nickname = {}
  events = []

  # Enter와 Leave 기록만 남겨 순서를 보존한다.
  for item in record:
    parts = item.split()
    command, uid = parts[0], parts[1]

    if command in ("Enter", "Change"):
      nickname[uid] = parts[2]

    if command != "Change":
      events.append((command, uid))

  answer = []
  # 남겨 둔 기록을 다시 순회하면서 최종 닉네임으로 메시지를 만든다.
  for command, uid in events:
    if command == "Enter":
      answer.append(f"{nickname[uid]}님이 들어왔습니다.")
    else:
      answer.append(f"{nickname[uid]}님이 나갔습니다.")

  return answer

시간 복잡도

N은 record의 길이이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.