파이썬 Python | 알고리즘 | 카카오 개발자 코딩테스트 및 오픈채팅방 알고리즘

 

⭕ 파이썬 Python | 알고리즘 | 카카오 개발자 코딩테스트 및 오픈채팅방 알고리즘

카카오의 핵심은 카카오톡입니다. 카카오의 신입 공개 채용 코딩 테스트 문제는 대학교 학부 과정에서 배우는 기초 알고리즘에 충실하지만, 문자열 기반 채팅 애플리케이션인 카카오톡은 카카오의 핵심인 만큼 문자열과 관련된 알고리즘이 항상 출제됩니다.

 

➡️ 2020년 카카오 개발자 신입 공개 채용 1차 1번 오픈채팅방 문제

[프로그래머스 문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/42888)

---

문제 설명

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있으며, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있습니다. 신입사원인 김크루는 카카오톡 오픈채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했습니다.

 

채팅방에 누군가 들어오면 다음 메시지가 출력됩니다:

•  "[닉네임]님이 들어왔습니다."

 

채팅방에서 누군가 나가면 다음 메시지가 출력됩니다:

• "[닉네임]님이 나갔습니다."

 

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경됩니다. 예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력됩니다:

• "Muzi님이 들어왔습니다."
• "Prodo님이 들어왔습니다."

 

Muzi가 나간 후 다시 들어올 때, Prodo라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경됩니다:

• "Prodo님이 들어왔습니다."
• "Prodo님이 들어왔습니다."
• "Prodo님이 나갔습니다."
• "Prodo님이 들어왔습니다."

 

채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있을 수 있습니다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경됩니다:

• "Prodo님이 들어왔습니다."
• "Ryan님이 들어왔습니다."
• "Prodo님이 나갔습니다."
• "Prodo님이 들어왔습니다."

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 `record`가 매개변수로 주어질 때, 모든 기록이 처리된 후 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 `solution` 함수를 완성하세요.

 

제한사항

• `record`는 길이가 1 이상 100,000 이하인 문자열 배열입니다.
• 각 문자열은 다음과 같은 형식을 가집니다:
  • "Enter [유저 아이디] [닉네임]" (ex. "Enter uid1234 Muzi")
  • "Leave [유저 아이디]" (ex. "Leave uid1234")
  • "Change [유저 아이디] [닉네임]" (ex. "Change uid1234 Muzi")
•  첫 단어는 Enter, Leave, Change 중 하나입니다.
• 모든 유저는 [유저 아이디]로 구분됩니다.
• 유저 아이디와 닉네임은 알파벳 대문자, 소문자, 숫자로만 이루어져 있으며, 길이는 1 이상 10 이하입니다.
• 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못된 입력은 주어지지 않습니다.

 

입출력 예

record = ["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"]
result = ["Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."]

 

 

➡️ 코드

def solution(record):
    answer = []  # 최종 결과를 저장할 리스트
    trace = []  # Enter와 Leave 기록을 저장할 리스트
    Map = {}  # 사용자 ID와 닉네임을 매핑할 딕셔너리

    for i in range(len(record)):
        temp = record[i].split(' ')  # 기록을 공백 기준으로 분리
        
        if temp[0] == 'Enter':  # 사용자가 입장한 경우
            Map[temp[1]] = temp[2]  # 사용자 ID와 닉네임을 저장
            trace.append([temp[0], temp[1]])  # 입장 기록 추가
        elif temp[0] == 'Leave':  # 사용자가 퇴장한 경우
            trace.append([temp[0], temp[1]])  # 퇴장 기록 추가
        else:  # 사용자가 닉네임을 변경한 경우
            Map[temp[1]] = temp[2]  # 사용자 ID와 새로운 닉네임을 저장

    for i in range(len(trace)):
        if trace[i][0] == 'Enter':  # 입장 기록을 처리할 때
            result = Map[trace[i][1]] + "님이 들어왔습니다."  # 입장 메시지 생성
            answer.append(result)  # 결과 리스트에 추가
        else:  # 퇴장 기록을 처리할 때
            result = Map[trace[i][1]] + "님이 나갔습니다."  # 퇴장 메시지 생성
            answer.append(result)  # 결과 리스트에 추가

    return answer  # 최종 결과 반환

 

➡️ 해설

백준 solved.ac 기준으로 난이도는 실버3 정도입니다. 이 문제는 맵 자료구조와 문자열 파싱 두 가지 개념을 이용하면 해결할 수 있습니다.

 

문제를 풀기 위한 핵심은 "유저 아이디는 중복되지 않으며 유저 아이디에 해당하는 닉네임은 중복을 허용한다"는 점입니다. 이러한 중복되지 않은 키 값에 따른 값을 저장하는 방법으로 맵 자료구조를 사용합니다. 맵은 키에 해당하는 값이 무엇인지 물어보면, 키 안에 들어 있는 값을 결과로 반환합니다.

 

입력 문자열은 [명령어, 유저 아이디, 닉네임] 형식으로 되어 있어 이를 다루기 까다롭습니다. 따라서, 공백을 기준으로 3가지 부분으로 나누어 다루기 편하게 만드는 것이 필요합니다. 이를 문자열 파싱이라고 합니다. 문자열 파싱을 통해 명령어, 유저 아이디, 닉네임을 분리하여 필요한 연산을 수행할 수 있습니다.

 

➡️ 시간복잡도

맵 자료구조는 시간 복잡도에서 O(log n)을 가집니다. 이는 집합의 크기가 n이고 집합이 오름차순 혹은 내림차순으로 정렬되어 있다면, 집합에서 원하는 값을 찾기까지 최대 O(log n)번 연산하면 된다는 의미입니다. 맵은 중복을 허용하지 않는 키와 키 안에 값을 저장하는 형식의 자료구조로, 키는 오름차순으로 정렬되어 있습니다.

 

맵 자료구조에서 키 값의 개수를 n이라고 할 때, 키 값에 접근할 때의 시간 복잡도는 O(log n)입니다. 키 값을 추가할 때의 시간 복잡도 또한 O(log n)입니다. 키 값을 추가할 때도 모든 키는 정렬된 상태를 유지합니다.

 

➡️ 카카오톡

카카오톡의 경우 1억 명 이상의 사용자가 있습니다. 

 

맵 자료구조를 사용하지 않은 경우

• 컴퓨터 연산 속도: 1초에 1억 번의 연산 가능
• 필요한 연산 계산
  • 전화번호(11자리) * 이름(3자리) = 33 
  • 1억 명 * 33 = 33억 연산
  • 33억 연산 / 1억(초당 연산 수) = 33초

따라서, 1억 명의 사용자가 카카오톡에 가입하는 데 약 33초가 걸립니다. 이는 단순히 가입에 필요한 시간이므로, 실제로는 더 많은 시간이 소요될 수 있습니다.

 

오픈채팅방에 들어가는 데 걸리는 시간

• 가입된 사용자 중 자신의 전화번호 찾기
  • 1억 명 / 1억(초당 연산 수) = 1초

즉, 오픈채팅방에 들어가는 데 평균적으로 1초가 걸립니다. 만약 오픈채팅방을 이용하는 모든 사용자가 1초씩 투자하여 대화를 참여한다면, 카카오톡의 서버는 과부화된 연산으로 인해 큰 부담을 겪게 될 것입니다.

 

맵 자료구조를 이용한 경우

• 맵 자료구조의 장점: 키-값 쌍을 효율적으로 저장하고 검색 가능
• 가입 시 필요한 연산 계산:
  • log2(1억) ≈ 26 (log2 계산)
  • 각 사용자가 가입할 때 필요한 연산: 전화번호(11자리) * 이름(3자리) = 33
  • 26 (로그 계산) * 33 = 858 연산
  • 858 연산 / 1억(초당 연산 수) = 0.00000858초

따라서, 맵 자료구조를 이용하면 1억 명의 사용자를 카카오톡에 가입시키는 데 약 0.00000858초가 걸립니다. 이는 단순 연산보다 훨씬 효율적입니다.

 

오픈채팅방에 들어가는 데 걸리는 시간

• 맵 자료구조 이용 시:
  • log2(1억) ≈ 26 (log2 계산)
  • 26 / 1억(초당 연산 수) = 0.00000026초

 

➡️ 회고

알고리즘을 공부하기 전에는 카카오톡의 오픈채팅방에 들어가는 데 몇 초가 걸릴지 한 번도 생각해 본 적이 없었어요. 하지만 알고리즘을 공부한 후, 제 생각의 틀이 완전히 바뀌었습니다. 이제는 잘 만들어진 어플을 보면, 이 어플의 기능이 어떤 알고리즘을 사용했는지 궁금해지기 시작했어요.

 

또한, 자료구조와 알고리즘이 프로그램의 속도에 얼마나 큰 영향을 미치는지 알게 되었어요.  이를 통해 효율적인 코드를 작성하는 방법과 시스템 성능을 최적화하는 중요성을 깨달았습니다.