개발자 아지트

문제설명

https://school.programmers.co.kr/learn/courses/30/lessons/42892

참고 

문제 해결 방법

주어진 리스트로 트리 만드는 부분 구현후, 스택을 활용해 트리 순회하는 코드 작성함 

후위 순회는 방문 여부를 체크 하도록 하여 구현하였음

코드 구현

def solution(nodeinfo):
    answer = []
    original = nodeinfo
    
    cnt = 0
    for i in nodeinfo:
        cnt +=1
        i.append(cnt)
    
    
    nodeinfo.sort(key = lambda x : (-x[1], x[0]))
    

    class Node:
        def __init__(self, key):
            self.left = None
            self.right = None
            self.val = key[2]
            self.x = key[0]
    
    class BST:
        def __init__(self):
            self.root = None
        
        def insert(self, key):
            if not self.root:
                self.root = Node(key)
            else:
                curr = self.root
                while 1:
                    if curr.x > key[0]:
                        if curr.left:
                            curr = curr.left
                        else:
                            curr.left = Node(key)
                            break
                    else:
                        if curr.right:
                            curr = curr.right
                        else:
                            curr.right = Node(key)
                            break
                    
        def preorder(self, result):
            curr = self.root
            stackk=[]
            stackk.append(curr)
            
            while 1:
                if len(stackk) != 0:
                    curr = stackk.pop()
                    
                    if curr is None:
                        continue
                    
                    result.append(curr.val)
                    stackk.append(curr.right)
                    stackk.append(curr.left)
                else:
                    break
            return result
                    
        def postorder(self, result):
            curr = self.root
            stackk=[(self.root, False)]
            # 이코드 대신 위에 코드 stackk.append(curr, False)
            
            while 1:
                if len(stackk) != 0:
                    curr, visited = stackk.pop()
                                      
                    if curr is None:
                        continue
                    if visited:
                        result.append(curr)
                    else:
                        stackk.append((curr.val, True))
                        stackk.append((curr.right, False))
                        stackk.append((curr.left, False))
                else:
                    break
            
            return result
    
    bst = BST()

    for key in nodeinfo:
        bst.insert(key)
        
    
    result = []
    answer.append(bst.preorder(result))
    result = []
    answer.append(bst.postorder(result))
    
    
    return answer

시간/공간 복잡도

O(N^2)

최적화 및 개선

하지않음

어려웠던 점

트리 구성 까지는 할 수 있는데, 트리 순회할때 재귀함수를 사용하지 않고 스택으로 구현하려니 어려웠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

문제 해결 방법

문제에서 미로를 탈출하는데 필요한 최소 시간을 구해야한다. 

최소 시간이나 최소 경로 등의 키워드, 노드의 간선에 가중치가 없는 경우,  BFS로 풀수 있다. 

코드 구현

from collections import deque
        
def solution(maps):
    answer = 0
    m = len(maps)
    n = len(maps[0])
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    q = deque()
    
    visited = []
    for i in range(len(maps)):
        listt = []
        for j in range(len(maps[0])):
            listt.append([False, False])
        visited.append(listt)
    
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                visited[i][j][0] = True
                q.append([i, j, 0, 0])
            elif maps[i][j] == 'E':
                endX = i
                endY = j

    while q:
        x, y, k, time = q.popleft()
        
        if k == 1 and endX == x and endY == y:
            return time
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]) or maps[nx][ny] == 'X':
                continue

            if maps[nx][ny] == 'L':
                if visited[nx][ny][1] == False:
                    visited[nx][ny][1] = True 
                    q.append([nx, ny, 1, time + 1])
                
            else:
                if visited[nx][ny][k] == False:
                    visited[nx][ny][k] = True 
                    q.append([nx, ny, k, time + 1])
                
    return -1

x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(rx, ry, cnt, maps, k, visited):
    for i in range(4):
        rx = rx + x[i]
        ry = ry + y[i]
        rx = int(rx)
        ry = int(ry)

        if rx < 0 or rx >= len(maps) or ry < 0 or ry >= len(maps[0]):
            continue

        if visited[rx][ry][k] == True or maps[rx][ry] == 'X' :
            continue

        if maps[rx][ry] == 'L':
            k = 1
        if k == 1 and maps[rx][ry] == 'E':
            return cnt
    
        
        #print(visited)
        if visited[rx][ry][k] == False:
            bfs(rx, ry, cnt, maps, k, visited)
            visited[rx][ry][k] = True
            cnt += 1
            
    return cnt       
                
        
def solution(maps):
    answer = 0
    m = len(maps)
    n = len(maps[0])
    
    #visited = [[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]
    
    visited = []
    for i in range(len(maps)):
        listt = []
        for j in range(len(maps)):
            listt.append([False, False])
            if maps[i][j] == 'S':
                startX = i
                startY = j
            elif maps[i][j] == 'L':
                laberX = i
                laberY = j
            elif maps[i][j] == 'E':
                endX = i
                endX = j
        
        visited.append(listt)
    
    #print('startX',startX,'startY', startY)
    #print(visited)
    
    k = 0
    print(bfs(startX, startY, 0, maps, k, visited))
                
            
            
            
    
    
    return answer

시간/공간 복잡도

O(N^2)

최적화 및 개선

queue말고 deque를 사용함

어려웠던 점

진짜 헤멧다. 문제를 풀다가 시간초과 했다. 

미로가 직사각형이 될 경우를 꼭 고려해야한다. 

처음에는 q를 사용하기 보단, 재귀함수만으로 문제를 구현하려고 했으나 실패하고 큐를 이용하여 문제를 풀었다. 

https://school.programmers.co.kr/learn/courses/30/lessons/77486

문제설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

문제 해결 방법

딕셔너리를 사용하여 문제를 해결함 

money의 10%는 money // 10을 한 값과 같음 

코드 구현

def solution(enroll, referral, seller, amount):
    answer = []

    dic = { }
    dic['-'] = []
    for i in enroll:
        if i in dic:
            continue
        else:
            dic[i] = []
    
    for i in range(len(referral)):
        key = enroll[i]
        dic[key] = referral[i]
    
    
    total = {name : 0 for name in enroll}
    
    for i in range(0, len(seller)):
        key = seller[i]
        
        money = amount[i] * 100
        
        curName = seller[i]
        
        while money > 0 and curName != '-':
            total[curName] +=money - money//10
            curName = dic[curName] # curName의 부모
            money = money//10
    
    
    return [total[name] for name in enroll]

시간/공간 복잡도

O(N*M)

N: enroll의 길이 

M: seller의 길이 

최적화 및 개선

따로 하지 않음

어려웠던 점

문제를 권장 시간안에 풀지 못했음, 부모 자식 관계 구현에 대해 서툴어서 문제 해결 방법을 생각해내지 못했음 

딕셔너리로 풀어야겠다는 생각을 늦게함

class Node:
    def __init__(self, key):
        self.left = None # 맨 처음 생성시 빈상태가 맞음 
        self.right = None # 맨 처음 생성시 빈상태가 맞음 
        self.val = key
       
class BST:
    def __init__(self):
        self.root = None
        
    def insert(self, key):
        if not self.root: #루트
            self.root = Node(key)
        else: # 루트가 있는 경우, 루트를 지정해주고 
            curr = self.root
            while True:
                # 루트보다 클것이냐 작을것이냐를 확인해보면,
                # 루트의 왼쪽부터 봐야하는지 오른쪽 부터 봐야하는지 알 수 있음
                if key < curr.val:
                    if curr.left:  
                        # 존재시 딱 현 위치 내려주는 것 까지만 하면됨.
                        # leaf노드 까지 가기위해서 이 작업을 하는 것임
                        curr = curr.left
                    else:
                        #leaf노드 도달 시 노드를 지정해줌 
                        curr.left = Node(key)
                        break
                else:
                    if curr.right:
                        curr = curr.right
                    else:
                        curr.right = Node(key)
                        break
    
    def search(self, key):
        # 서치도 루트부터 시작함. 현위치 잡는 변수를 항상 만들것. 
        curr = self.root
        while curr and curr.val != key:
        
            if key < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        
        return curr
                


def solution(lst, search_lst):
    # 이진 탐색 트리 생성
    # search_lst의 각 노드를 이진 탐색트리에서 찾을 수 있는지 여부 반환 리스트 반환
    result = []

    bst = BST() # 객체 생성

    for key in lst:
        bst.insert(key) # bst객체가 insert메서드 호출 
    
    for search in search_lst:
        if bst.search(search):
            result.append(True)
        else:
            result.append(False)


    print(result)

    return result

class Node: #노드
    def __init__(self, key):
        self.left = None 
        self.right = None 
        self.val = key

class BST: # 이진트리 클래스 
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            curr = self.root
            while 1:
                if curr.val > key:
                    if curr.left:
                        curr = curr.left
                    else:
                        curr.left = Node(key)
                        break
                else:
                    if curr.right:
                        curr = curr.right
                    else:
                        curr.right = Node(key)
                        break

    def search(self, key):
        curr = self.root
        print('curr', curr)
        while curr and curr.val != key:
            if curr.val > key:
                curr = curr.left
            else:
                curr = curr.right

        return curr 
            


def solution(lst, search_lst):
    bst = BST()

    for key in lst:
        bst.insert(key)
    
    result = []
    for searchVal in search_lst:
        if bst.search(searchVal):
            result.append(True)
        else:
            result.append(False)

    return result

def preorder(nodes, idx, result):
    if len(nodes)>idx:
        result.append(nodes[idx])
        preorder(nodes, (idx * 2) + 1, result)
        preorder(nodes, (idx * 2) + 2, result)
    return result

def inorder(nodes, idx, result):
    if len(nodes)>idx:
        inorder(nodes, (idx * 2) + 1, result)
        result.append(nodes[idx])
        inorder(nodes, (idx * 2) + 2, result)
    return result

def postorder(nodes, idx, result):
    if len(nodes)>idx:
        postorder(nodes, (idx * 2) + 1, result)
        postorder(nodes, (idx * 2) + 2, result)
        result.append(nodes[idx])
    return result

def solution(nodes):
    # 전위, 중위, 후위 순회 결과 계산
    # 노드 리스트와 루트 노드의 인덱스를 매개변수로 각각 호출
    
    preorderNodes = []
    inorderNodes = []
    postorderNodes = []

    preorderNodes = preorder(nodes, 0, preorderNodes) # 전위
    inorderNodes = inorder(nodes, 0, inorderNodes)
    postorderNodes = postorder(nodes, 0, postorderNodes)

    preorderNodesresult = " ".join(map(str,preorderNodes))
    inorderNodesresult = " ".join(map(str,inorderNodes))
    postorderNodesresult = " ".join(map(str,postorderNodes))

    total = []
    total.append(preorderNodesresult)
    total.append(inorderNodesresult)
    total.append(postorderNodesresult)
    
    return total

https://school.programmers.co.kr/learn/courses/30/lessons/12985

문제설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

문제 해결 방법

구조를 그리고 보면 이진트리 형태이다. 이진트리에 인덱스를 어떤식으로 붙이는지를 생각해보면서 문제를 풀었다. 

코드 구현

def solution(n,a,b):
    answer = 0
    cnt = 0
    while a !=b:
        a = (a+1)//2
        b = (b+1)//2
        cnt+=1
    return cnt

시간/공간 복잡도

O(logN)

최적화 및 개선

따로 하지 않음

어려웠던 점

해시 인덱스 개념이 잘 와닿지 않아서 인덱스를 수식으로 생각해볼 생각을 못했음 

https://school.programmers.co.kr/learn/courses/30/lessons/72411

문제설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.

기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,

(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

문제 해결 방법

조합을 사용하여 문제를 해결함 

코드 구현

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    
    menu = []
    for ii in course:
        for i in orders:
            for j in combinations(i, ii):
                a = []
                a = sorted(list(j))
                menu.append(tuple(a))
                
        counter = Counter(menu)
        if len(counter) > 0:
            maxx = max(counter.values())
        if maxx>1:
            for i in counter.items():
                if maxx == i[1]:
                    answer.append(''.join(list(i[0])))
        
        menu = []
    answer=sorted(answer)
    return answer

시간/공간 복잡도

O(N*2^M)

최적화 및 개선

따로 하지 않음

어려웠던 점

조합 및 Counter사용 방법을 몰라서 헤메었음 

https://school.programmers.co.kr/learn/courses/30/lessons/92334

문제설명

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.

• 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
• 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.

k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.

• 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

문제 해결 방법

해시를 통해 문제를 해결함

코드 구현

def solution(id_list, report, k):
    answer = []
    
    singoList = { }
    amISingo = { }
    
    for i in id_list:
        if i in singoList:
            continue
        else:
            singoList[i] = []
            amISingo[i] = 0
    
    for i in report:
        tmpList = i.split(" ")
        if tmpList[0] in singoList:
            key = tmpList[0]
            
            values = singoList.get(key)
            if tmpList[1] in values:
                continue
            else:
                singoList[key].append(tmpList[1])
                
    for i in singoList:
        tmpList = singoList[i]
        if len(tmpList) > 0:
            for j in tmpList:
                if j in amISingo:
                    amISingo[j]+=1
                else:
                    continue

    realSingoMan = []
    
    for i in amISingo:
        if amISingo[i] >=k:
            realSingoMan.append(i)

    for i in singoList:
        tmpValue = singoList[i]

        cnt = 0
        for j in tmpValue:
            if j in realSingoMan:
                cnt+=1

        answer.append(cnt)
        cnt=0

    return answer

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지 않음

어려웠던 점

없음

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.

장르 내에서 많이 재생된 노래를 먼저 수록합니다.

장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

문제 해결 방법

기본적으로 해시의 개념을 사용하였고, 람다를 사용하여 해시를 정렬하였음

코드 구현

def solution(genres, plays):
    answer = []
    
    newList = []
    for i in range(len(genres)):
        list=[]
        list.append(i)
        list.append(genres[i])
        list.append(plays[i])
        
        newList.append(list)

    playsHash = { }
    for i in newList:
        key = i[1]
        if i[1] in playsHash:
            playsHash[key]+=i[2]
        else:
            playsHash[key]=i[2]

    list = []
    list = sorted(playsHash, key= lambda x:playsHash[x], reverse=True)

    
    Nlist=[]
    for i in list:
        case = []
        for j in newList:
            if i==j[1] :
                nlist = []
                nlist.append(j[0])
                nlist.append(j[2])
                case.append(nlist)
        Nlist.append(case)
    
    for i in Nlist:
        i.sort(key = lambda x:(x[1], -x[0]), reverse = True)
        cnt = 0
        for j in i:
            if cnt == 2:
                break
            answer.append(j[0])
            cnt+=1
    
    return answer

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지 않음

어려웠던 점

람다를 다루는 것이 익숙치 않아서 어려웠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42888

문제설명

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

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

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

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

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.

채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

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

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

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

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

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

"Muzi님이 나갔습니다."

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

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

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

"Prodo님이 나갔습니다."

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

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

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

"Ryan님이 들어왔습니다."

"Prodo님이 나갔습니다."

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

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

제한사항

record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.

다음은 record에 담긴 문자열에 대한 설명이다.

모든 유저는 [유저 아이디]로 구분한다.

[유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - "Enter [유저 아이디] [닉네임]" (ex. "Enter uid1234 Muzi")

[유저 아이디] 사용자가 채팅방에서 퇴장 - "Leave [유저 아이디]" (ex. "Leave uid1234")

[유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - "Change [유저 아이디] [닉네임]" (ex. "Change uid1234 Muzi")

첫 단어는 Enter, Leave, Change 중 하나이다.

각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.

유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.

유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.

채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

문제 해결 방법

해시로 문제를 풀었음

코드 구현

def solution(record):
    answer = []
    newList = []
    
    for i in range(len(record)):
        newList.append(record[i].split(" "))
    
    uidName = { }
    
    for i in newList:
        if len(i) == 3:
            if i[1] in uidName:
                key = i[1]
                uidName[key] = i[2]
            else:
                key = i[1]
                uidName[key] = i[2]
    
    for i in newList:
        if i[1] in uidName:
            key = i[1]
            if i[0] == 'Enter':
                answer.append(uidName[key]+"님이 들어왔습니다.")
            elif i[0] == 'Leave':
                answer.append(uidName[key]+"님이 나갔습니다.")
            else:
                continue

    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

따로 하지 않음

어려웠던 점

없음