[5월 4주차] 2문제 풀이

[구현] 이중우선순위큐 (Lv.2)

접근 방식

제목은 이중우선순위큐지만 단순한 구현 문제다.
문제의 조건에 맞는 자료구조를 구현하면 된다.

정답 코드

class queue:
    def __init__(self):
        self.data = []
    def insert(self, data):
        self.data.append(data)
        return True
    def is_empty(self):
        if len(self.data) == 0:
            return True
        return False
    def del_max(self):
        if self.is_empty():
            return False
        self.data.remove(max(self.data))
        return True
    def del_min(self):
        if self.is_empty():
            return False
        self.data.remove(min(self.data))
        return True
    def print_max(self):
        if self.is_empty():
            return 0
        return max(self.data)
    def print_min(self):
        if self.is_empty():
            return 0
        return min(self.data)
    def print_queue(self):
        print(self.data)

def solution(operations):
    q = queue()
    for o in operations:
        oper, num = o.split(" ")
        if oper == "I":
            q.insert(int(num))
            q.print_queue()
        else:
            if num == "1":
                q.del_max()
            else:
                q.del_min()
            q.print_queue()

    return [q.print_max(), q.print_min()]

배운점

[DP] 매출 하락 최소화 (Lv.4) (해설참고함)

접근 방식

처음에는 접근조차 어려웠다.
포함되냐 안되냐의 차이로 생각해야 될 분기가 너무 많아서 복잡했다.

단순하게 모든 팀이 다 들을 수 있는 멤버 구성이 되는 것을 완료조건으로 잡아 DFS로 풀어보고자 했다.
sales 배열의 최댓값이 300,000이라 시간초과가 날 것 같았지만 일단 부딪혀봤다.

한 팀에 어떤 직원idx가 있는지 알려주는 group_to_idx 딕셔너리와
해당 직원이 어느 팀에 속해있는지 알려주는 idx_to_group 딕셔너리,
DFS로 풀기 위해 visitedGroup 배열로 DFS로 풀어봤지만 소용없었다.

시도한 코드

from collections import deque
from tokenize import group

class Node:
    def __init__(self, idx, sales):
        self.idx = idx
        self.sales = sales
        self.children = []
        self.parent = None

class Tree:
    def __init__(self, sales, links):
        self.nodes = [Node(i, sales[i]) for i in range(len(sales))]
        for leader, member in links:
            self.nodes[leader-1].children.append(self.nodes[member-1])
            self.nodes[member-1].parent = self.nodes[leader-1]
        root = self.nodes[0]
        while True:
            if root.parent is None:
                break
            root = root.parent
        self.root = root

# 트리를 한번 돌면서 그룹에 해당하는 멤버들의 idx를 모아둔 array를 만든다.
def grouping(tree):
    group_to_idx = {}
    idx_to_group = {}
    
    queue = deque([tree.root])
    i = 0
    while queue:
        current = queue.popleft()
        group_to_idx[i] = [current.idx] + [child.idx for child in current.children]
        for idx in group_to_idx[i]:
            if idx_to_group.get(idx) is not None:
                idx_to_group[idx].append(i)
            else:
                idx_to_group[idx] = [i]
        queue.extend(current.children)
        i += 1

    return group_to_idx, idx_to_group

def dfs(group_idx, visitedGroup, group_to_idx, idx_to_group, dict_sales):
    # 현재 조사하는 그룹을 vistedGroup 체크
    visitedGroup[group_idx] = True
        
    # 조사하는 그룹의 팀장 및 팀원을 하나하나 체크하면서 vistedGroup을 체크한 뒤 다음 그룹으로 넘어간다.
    min_sales = float('inf')
    for idx in group_to_idx[group_idx]:
        for i in idx_to_group[idx]:
            visitedGroup[i] = True
        if all(visitedGroup):
            min_sales = min(min_sales, dict_sales[idx])
        else:
            # 방문 안한 그룹을 조사
            for i in range(group_idx+1, len(visitedGroup)):
                if not visitedGroup[i]:
                    min_sales = min(min_sales, dfs(i, visitedGroup, group_to_idx, idx_to_group, dict_sales))
        for i in idx_to_group[idx]:
            visitedGroup[i] = False
    return min_sales


def solution(sales, links):
    tree = Tree(sales, links)
    # 트리를 한번 돌면서 그룹에 해당하는 멤버들의 idx를 모아둔 array를 만든다.
    group_to_idx, idx_to_group = grouping(tree)
    visitedGroup = [False for _ in range(len(group_to_idx))]

    # sales에 해당하는 dict를 만든다.
    dict_sales = {}
    for i in range(len(sales)):
        dict_sales[i] = sales[i]

    # [[1,9,5,3], [9,7], [5,4,10], [10,6,8,2]]
    # 1. 그룹의 멤버들을 다 돌아본다.
    # 1-1. 그룹의 멤버 idx와 idx_to_group을 사용하여 visitedGroup을 체크한다.
    # 1-2. 다음 그룹 중 visitedGroup이 False인 그룹이 있다면 그 그룹으로 들어간다.
    # 2. 만약 그룹을 다 돌아봤으면 최솟값을 갱신한다.
    
    answer = dfs(0, visitedGroup, group_to_idx, idx_to_group, dict_sales)

    return answer

배운 점

이 문제는 다양한 분기가 있어서 전수조사를 해야할 것 같았지만 DP를 통해 풀 수 있었다.
그리고 시작점을 루트노드가 아닌 밑바닥(Leaf 노드)에서부터 올라오도록 조사하는 방법이다.

1. 팀장 $P$가 워크숍에 참석하는 경우 (dp[P][1])
팀장이 참석했기에 자식은 참여하든 참여하지 않든 상관이 없다.
고로 참여O와 참여X 중 더 작은 비용을 누적한다.
$dp[P][1] = sales[P] + \sum \min(dp[C][0], dp[C][1])$

2. 팀장 $P$가 워크숍에 참석하지 않는 경우 (dp[P][0])
팀장이 불참이므로 팀원 중 한 명 이상이 참석해야한다.

• 2-1. 이미 참석한다는 자식이 있을 경우
  dp[C][0]보다 dp[C][1]이 더 작아서 스스로 참석(1)을 선택한 자식이 한명이라도 있다면
  그냥 그 자식(들)의 최소 비용만 다 더해주면 된다.
  $\sum \min(dp[C][0], dp[C][1])$

• 2-2. 자식들이 전부 다 안 가겠다고 하는 경우 (dp[C][0] < dp[C][1])
  자식들이 전부 dp[C][0]이 더 작다면 아무도 워크숍에 가지 못한다.
  그래서 참석할 때와 안 할 때의 차이(dp[C][1] - dp[C][0])가 가장 작은 자식 한 명을 골라 강제로 참여시켜야 한다.

다음은 이를 파이썬으로 구현한 코드이다.

import sys
# 재귀 깊이 제한 해제 (프로그래머스 등 코테 환경 필수)
sys.setrecursionlimit(100000)

def solution(sales, links):
    # 1. 트리 인접 리스트 생성 (1번 인덱스부터 사용)
    n = len(sales)
    adj = [[] for _ in range(n + 1)]
    for leader, member in links:
        adj[leader].append(member)
        
    # 2. DP 테이블 초기화: dp[i][0]은 불참, dp[i][1]은 참석
    dp = [[0, 0] for _ in range(n + 1)]

    def dfs(node):
        # 매출액은 인덱스가 0부터 시작하므로 sales[node-1]
        dp[node][1] = sales[node - 1]
        dp[node][0] = 0
        
        # 자식이 없는 리프 노드라면 그대로 종료 (Base Case)
        if not adj[node]:
            return

        total_sub_sum = 0
        is_child_attended = False
        min_diff = float('inf')

        # 자식들을 먼저 순회 (Post-order)
        for child in adj[node]:
            dfs(child)
            
            # 자식들의 최적 비용을 누적
            total_sub_sum += min(dp[child][0], dp[child][1])
            
            # 자식 중 한 명이라도 참석(1)하는 게 이득이었는지 확인
            if dp[child][1] <= dp[child][0]:
                is_child_attended = True
            
            # 강제 참석 시 추가되는 최소 비용(차액) 계산
            min_diff = min(min_diff, dp[child][1] - dp[child][0])

        # 부모가 참석하는 경우
        dp[node][1] += total_sub_sum

        # 부모가 참석하지 않는 경우
        if is_child_attended:
            # 자식 중 이미 간 사람이 있다면 그대로 누적
            dp[node][0] = total_sub_sum
        else:
            # 아무도 안 갔다면 가장 차액이 적은 자식을 강제로 보냄
            dp[node][0] = total_sub_sum + min_diff

    # 1번 노드(CEO/루트)부터 DFS 시작
    dfs(1)
    
    # 루트 노드가 참여했을 때와 참여하지 않았을 때 중 최솟값 반환
    return min(dp[1][0], dp[1][1])

해설을 보면 해결방법이 정갈하지만 문제를 보고 이렇게 DP로 나눌 수 있는 내공이 아직 부족한 것 같다. 특히 케이스 2-2로 최소비용을 구하는 것이 그냥 생각해내기엔 어려운 것 같다.
그래서 Lv.4인가
프로그래머스 추천 문제로 나온 문제라 일단 풀어봐야지 하고 풀어봤다가 꽤나 시간이 걸렸다.
당분간은 Lv.3를 상한선으로 둬야할 것 같다...