개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/12981?language=python3

문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.

마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

이전에 등장했던 단어는 사용할 수 없습니다.

한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.

2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.

3번 사람이 자신의 첫 번째 차례에 know를 말합니다.

1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.

(계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.

단어의 길이는 2 이상 50 이하입니다.

모든 단어는 알파벳 소문자로만 이루어져 있습니다.

끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.

정답은 [ 번호, 차례 ] 형태로 return 해주세요.

만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

문제 해결 방법

문제를 풀기위한 조건들을 하나하나 생각해서 하나하나 제외해가면서 풀었음

코드 구현

def solution(n, words):
    answer = []
    # 1번부터 마지막 순서까지 돌고돈다.
    # 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야한다. 
    # 이전에 등장했던 단어는 사용할 수 없다. 
    # 한 글자 단어 인정안해줌
    newWords=[] #스택에 쌓음
    newWords.append(words[0]) 
    
    cnt = 1 #words에서 어디를 가리키는지 
    big_phase=0
    check = 0
    check2 = 0
    while 1:
        big_phase+=1
        for i in range(1, n+1):
            if check ==1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if check2 == 1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if cnt == len(words):
                break
            
            if words[cnt][0] == newWords[-1][-1]:
                pass
            else:
                check = 1
                
            
            if words[cnt] in newWords:
                check2 = 1
            else:
                newWords.append(words[cnt])  
                cnt+=1
                
        if cnt == len(words):
                break

    answer.append(0)
    answer.append(0)
    
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

최적화 및 개선하지 않음

어려웠던 점

예전에 작성한 코드랑 그닥 로직이 다른거 같진 않다.. 

스스로 더 로직을 잘 이해하고 풀었다는 차이점이 존재할뿐? 

문제설명

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)

최적화 및 개선

따로 하지 않음

어려웠던 점

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