99클럽 코테 스터디 8일차 TIL - 좀 더 구조화된 답을 내보자

 

오늘 배운 점

중복코드는 함수화해보자.

문제1 - 이중 우선순위 큐 문제링크

문제 설명

이중 우선순위 큐를 구현해야 한다. 이중 우선순위큐란 큐 내의 최댓값과 최솟값을 모두 구할 수 있는 자료구조입니다.

3가지 연산이 주어집니다.

풀이 과정

일단, 우선순위 큐 하나만 가지고는 최대힙이나 최소힙 하나만 구현할 수 있을거라고 생각해서 최대힙, 최소힙을 각각 하나씩 가지는 Depq 클래스를 만들었습니다. 이후 숫자를 삽입할 땐 양 쪽 힙에 모두 넣어주고, 최댓값을 제거할 땐 최대힙에서 pop하고, 최솟값을 제거할 땐 최소힙에서 pop하면 되겠다고 생각했습니다.

하지만 이대로 코드를 작성한다면 한쪽 힙에서 제거한 숫자가 여전히 다른쪽 힙에 남아있게 되기 때문에 추가 작업이 필요했습니다.

그래서 각각의 힙에서 삭제된 숫자 정보를 담는 딕셔너리를 이용하여 추후 해당 딕셔너리를 참고해서 이미 삭제된 숫자인지 판단하도록 구현하였습니다.

 

정답코드1

import heapq
from collections import defaultdict
class Depq:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []
        self.max_heap_removed = defaultdict(int)
        self.min_heap_removed = defaultdict(int)
    
    def removeMax(self):
        while self.max_heap and self.min_heap_removed[-self.max_heap[0]] > 0:
            self.min_heap_removed[-self.max_heap[0]] -= 1
            heapq.heappop(self.max_heap)
        
        if self.max_heap:
            val = -heapq.heappop(self.max_heap)
            self.max_heap_removed[val] += 1
        
        while self.min_heap and self.max_heap_removed[self.min_heap[0]] > 0:
            self.max_heap_removed[self.min_heap[0]] -= 1
            heapq.heappop(self.min_heap)
    
    def removeMin(self):
        while self.min_heap and self.max_heap_removed[self.min_heap[0]] > 0:
            self.max_heap_removed[self.min_heap[0]] -= 1
            heapq.heappop(self.min_heap)
        
        if self.min_heap:
            val = heapq.heappop(self.min_heap)
            self.min_heap_removed[val] += 1
        
        while self.max_heap and self.min_heap_removed[-self.max_heap[0]] > 0:
            self.min_heap_removed[-self.max_heap[0]] -= 1
            heapq.heappop(self.max_heap)
        
            
    def insert(self, val):
        heapq.heappush(self.max_heap, -val)
        heapq.heappush(self.min_heap, val)
    
    def getMax(self):
        while self.max_heap and self.min_heap_removed[-self.max_heap[0]] > 0:
            self.min_heap_removed[-self.max_heap[0]] -= 1
            heapq.heappop(self.max_heap)
            
        return -self.max_heap[0] if self.max_heap else 0
    def getMin(self):
        while self.min_heap and self.max_heap_removed[self.min_heap[0]] > 0:
            self.max_heap_removed[self.min_heap[0]] -= 1
            heapq.heappop(self.min_heap)
        return self.min_heap[0] if self.min_heap else 0
        
def solution(operations):
    answer = []
    
    depq = Depq()
    
    for op in operations:
        splitted = op.split(' ')
        
        if splitted[0] == 'I':
            depq.insert(int(splitted[1]))
        elif splitted[0] == 'D' and splitted[1] == '1':
            depq.removeMax()
        else:
            depq.removeMin()
    return [depq.getMax(), depq.getMin()]

위 코드에서 앞서 언급한 이미 지워진 숫자를 제거하는 로직이 이중 우선순위 큐 내 대부분의 메서드에 사용되는 것을 볼 수 있습니다.

이를 하나의 헬퍼함수로 따로 구현한 후 사용한다면 좀 더 중복이 제거된 코드를 작성할 수 있어보입니다.

 

정답코드 2

import heapq

REMOVED = "r"


class DoublePriorityQueue:

    def __init__(self):

        self.entry_finder = {}
        self.min_heap = []
        self.max_heap = []
        self.cnt = 0

    def _check_empty(self, q) -> bool:
        while q and q[0][1] == REMOVED:
            heapq.heappop(q)
        if not q:
            return True
        return False

    def insert(self, v):
        vid = self.cnt
        min_ele, max_ele = [v, vid], [-v, vid]
        heapq.heappush(self.min_heap, min_ele)
        heapq.heappush(self.max_heap, max_ele)
        self.entry_finder[vid] = [min_ele, max_ele]
        self.cnt += 1

    def pop_min(self):
        is_empty = self._check_empty(self.min_heap)
        if not is_empty:
            value, vid = heapq.heappop(self.min_heap)
            entries = self.entry_finder.pop(vid)
            entries[1][1] = REMOVED

    def pop_max(self):
        is_empty = self._check_empty(self.max_heap)
        if not is_empty:
            value, vid = heapq.heappop(self.max_heap)
            entries = self.entry_finder.pop(vid)
            entries[0][1] = REMOVED

    def get_min(self):
        if not self._check_empty(self.min_heap):
            return self.min_heap[0][0]
        return 0

    def get_max(self):
        if not self._check_empty(self.max_heap):
            return - self.max_heap[0][0]
        return 0


def solution(operations):
    dpq = DoublePriorityQueue()

    for each in operations:
        op, num = each.split(" ")
        num = int(num)
        if op == "I":
            dpq.insert(num)
        elif op == "D" and num == -1:
            dpq.pop_min()
        else:
            dpq.pop_max()

    return [dpq.get_max(), dpq.get_min()]

위 코드는 정답 코드 중 제가 생각한 방향과 일치하되 좀 더 정돈된 것으로 보여 가져와 보았습니다.

숫자를 힙에 넣을 때 [값, 순서] 리스트를 넣고 해당 리스트를 따로 딕셔너리에 저장해 놓습니다.

이후, 최솟값 혹은 최댓값을 삭제해야 할 때 해당 값이 이미 삭제된 값인지 확인하고 지워주는 check_empty를 필요한 곳에서 호출해 사용합니다.

 

문제 2 - 다단계 칫솔 판매 문제링크

문제 설명

칫솔 다단계 회사에서 돈을 벌 수 있는 방법은 두 가지입니다.

첫 번째로, 개당 100원인 칫솔을 판매하기

두 번째로, 자신을 통해 회사에 입사한 사람이 전해주는 수수료를 받기

위 두 가지 수단 모두 자신이 90%를 가지고 나머지 10%는 자신을 추천한 사람에게 주어야 합니다.

이때 모든 칫솔 판매 이후 회사 직원들이 번 이익금을 직원별로 각각 구하는 문제입니다. 

 

풀이 과정

우선, 다단계는 가계부처럼 나의 조상의 조상이 있는 구조이기 때문에 나와 나를 추천한 사람을 키-값으로 묶기 위해 딕셔너리를 사용했습니다. 이후 각각의 판매실적에 대해 90%의 자기 몫과 나머지 10%를 상위로 전달하는 과정을 재귀적으로 수행하면 될 것 같았습니다.

from collections import defaultdict
def calculate(seller, amount, pyramid, profits):
    if seller == '-':
        return
    
    upper = amount / 10
    
    
    if upper < 1:
        profits[seller] += amount
        return
        
    profits[seller] += amount - int(upper)
    calculate(pyramid[seller], int(upper), pyramid, profits)
    
def solution(enroll, referral, seller, amount):
    answer = []

    pyramid = defaultdict(str)
    profits = defaultdict(int)
    
    for i in range(len(enroll)):
        pyramid[enroll[i]] = referral[i]
    
    for i in range(len(seller)):
        calculate(seller[i], amount[i] * 100, pyramid, profits)
    
    for name in enroll:
        answer.append(profits[name])
    return answer

calculate 함수의 종료조건은 더이상 수수료를 넘겨줄 조상이 없는 경우이거나, 넘겨줄 수수료가 1원 미만일 경우입니다.

1원 미만인 경우를 체크할 때, 10으로 나누어 정제되지 않은 수수료를 구해 체크하고 이후에 int로 1원 단위만 취하는 과정이 까다로웠습니다.

 

총평

중복 코드는 함수화해보자.

이중 우선순위 큐는 최대힙, 최소힙으로 구현하는 방법 뿐 아니라 Interval힙, Pairing힙, 균형이진트리 등 다양한 방법이 있습니다. 

파이썬의 리스트를 인자로 넣으면 call by reference로 넘겨져서 외부 리스트를 조작할 수 있습니다.