[프로그래머스] #힙 #Level3 이중우선순위큐

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operations	return
[I 16,D 1]	[0,0]
[I 7,I 5,I -5,D -1]	[7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

풀이

def solution(operations):
    answer = []
    
    for operation in operations:
        if operation.startswith("I"):
            answer.append(int(operation[2:]))
            answer.sort()
            
        elif len(answer) == 0:
            continue
            
        elif operation == "D -1":
            answer.pop(0)
            
        else:
            answer.pop()
        
    return [answer[-1], answer[0]] if len(answer) > 0 else [0, 0]

자료구조라는 개념에 얽매이면 지는 문제...
시간이 촉박한 것도 아니라 양방향으로 pop 할 수 있는 자료구조면 됩니다.

from heapq import heappush, heappop

def solution(arguments):
    max_heap = []
    min_heap = []
    for arg in arguments:
        if arg == "D 1":
            if max_heap != []:
                heappop(max_heap)
                if max_heap == [] or -max_heap[0] < min_heap[0]:
                    min_heap = []
                    max_heap = []
        elif arg == "D -1":
            if min_heap != []:
                heappop(min_heap)
                if min_heap == [] or -max_heap[0] < min_heap[0]:
                    max_heap = []
                    min_heap = []
        else:
            num = int(arg[2:])
            heappush(max_heap, -num)
            heappush(min_heap, num)
    if min_heap == []:
        return [0, 0]
    return [-heappop(max_heap), heappop(min_heap)]

정석 풀이. python의 heapq 모듈을 사용하여 일반 배열을 heappush, heappop을 통해 힙처럼 관리할 수 있습니다. max_heap, min_heap을 두고 한 힙이 []일 경우에만 두 힙을 동기화 하는 방식으로 관리합니다. heapq 모듈은 최소 힙 기능만 지원하기 때문에 입력할 수를 음수로 전환하여 최대 힙처럼 사용한 케이스입니다.

from heapq import heappush, heappop
from collections import deque

class Node:
    def __init__(self,value,left=None,right=None):
        self.value,self.left,self.right= value,left,right
class BST:
    def __init__(self,head):
        self.head= head # node

    # insert
    def insert(self,value):
        if not self.head:
            self.head= Node(value)
            print(value,'노드 없어서 노드 만들어줌.')
            return True
        self.cn = self.head # current_node
        while self.cn:
            if value < self.cn.value:
                if self.cn.left:    
                    self.cn= self.cn.left
                else:
                    self.cn.left= Node(value)
                    print(value,'왼쪽에 추가')
                    return True
            else:
                if self.cn.right:
                    self.cn= self.cn.right
                else:
                    self.cn.right= Node(value)
                    print(value, '오른쪽에 추가')
                    return True
    # delete
    def delete_max(self):
        if not self.head:
            print('빈 큐라 삭제 못함')
            return 'empty'

        if not self.head.left and not self.head.right:
            self.head= None
            return

        if self.head.left and not self.head.right:
            self.head= self.head.left
            return

        # 가장 오른쪽에 있는 노드 제거.
        self.p= self.head
        self.cn= self.head

        while self.cn.right:
            self.p= self.cn
            self.cn= self.cn.right

        ## leaf node인 경우
        if not self.cn.left:
            self.p.right= None
            #del self.cn
            print('삭제')
            return True
        ## left node를 가지는 경우
        elif self.cn.left:
            self.p.right= self.cn.left
            #del self.cn
            print('삭제')
            return True

    def delete_min(self):
        if not self.head:
            return 'empty'
        if not self.head.left and not self.head.right:
            self.head= None
            return

        if not self.head.left and self.head.right:
            self.head= self.head.right
            return

        # 가장 왼쪽에 있는 노드 제거.
        self.p= self.head
        self.cn= self.head

        while self.cn.left:
            self.p= self.cn
            self.cn= self.cn.left

        ## leaf node인 경우
        if not self.cn.right:
            self.p.left= None
            #del self.cn
            print('삭제')
            return True
        ## right node를 가지는 경우
        elif self.cn.left:
            self.p.left= self.cn.right
            #del self.cn
            print('삭제')
            return True 

    def search(self):

        max_min= [0,0]
        if not self.head:
            return max_min

        # 가장 왼쪽에 있는 노드 찾기.
        self.p= self.head
        self.cn= self.head
        while self.cn.left:
            print('p',self.p.value)
            print('cn',self.cn.value)
            self.p= self.cn
            self.cn= self.cn.left
        max_min[1]= self.cn.value

        # 가장 오른쪽에 있는 노드 찾기.
        self.p= self.head
        self.cn= self.head
        while self.cn.right:
            print('p',self.p.value)
            print('cn',self.cn.value)
            self.p= self.cn
            self.cn= self.cn.right
        max_min[0]= self.cn.value    
        return max_min

def solution(operations):

    bst= BST(None)
    for o in operations:
        if o[0] == 'I':
            bst.insert(int(o[2:]))
        elif o == 'D -1':
            bst.delete_min()
        elif o == 'D 1':
            bst.delete_max()

    return bst.search()

길어지지 않아도 괜찮아요:0...