데크, 우선순위 큐

Question 26: 원형 데크 디자인

입력:
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);
myCircularDeque.insertLast(2);
myCircularDeque.insertFront(3);
myCircularDeque.insertFront(4);
myCircularDeque.getRear();

myCircularDeque.isFull();

myCircularDeque.deleteLast();

myCircularDeque.insertFront(4);
myCircularDeque.getFront();

출력:
True
True
True
False
2
True
True
True
4

내 풀이

class MyCircularDeque:

    def __init__(self, k: int):
        self.d = [None] * k
        self.front = 0
        self.last = 0
        self.maxlen = k

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False          
        else:
            self.d[self.front] = value
            self.front = self.front % self.maxlen - 1
            return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():            
            return False        
        else:
            self.last = self.last % self.maxlen + 1
            self.d[self.last] = value
            return True
        
    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.d[self.front] = None
            self.front = self.front % self.maxlen + 1
            return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.d[self.last] = None
            self.last = self.last % self.maxlen - 1
            return True
        
    def getFront(self) -> int:
        if self.isEmpty() == True:
            return -1
        else:
            return self.d[self.front+1]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.d[self.last]

    def isEmpty(self) -> bool:
        empty = 0
        for i in self.d:
            if i == None:
                empty += 1
        return True if empty == len(self.d) else False
                

    def isFull(self) -> bool:
        if None not in self.d:
            return True
        else:
            return False
            

• 이전에 원형 큐 코드를 짤 때 사용하였던 투 포인터 방식, front와 last를 지정해서 값이 추가되거나 제거될때마다 위치가 바뀌는 방법으로 풀었다.
• 원형 데크의 크기가 1이 될 때를 고려하지 않아 결국 에러가 떴다.

결과

IndexError: list assignment index out of range

---

풀이 1: 이중 연결 리스트를 이용한 데크 구현

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head

    # 이중 연결 리스트에 신규 노드 삽입
    def _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new

    def _del(self, node: ListNode):
        n = node.right.right
        node.right = n
        n.left = node

    def insertFront(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.tail.left, ListNode(value))
        return True

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True

    def getFront(self) -> int:
        return self.head.right.val if self.len else -1

    def getRear(self) -> int:
        return self.tail.left.val if self.len else -1

    def isEmpty(self) -> bool:
        return self.len == 0

    def isFull(self) -> bool:
        return self.len == self.k

중요 내용

• 연결리스트인 head와 tail이 이중으로 연결 되어있음을 이용한 풀이 방법이다.
• insertFront는 self.head 다음에 ListNode(value) 값을 추가한다.
• insertLast는 tail.left 다음에 ListNode(value) 값을 추가한다.
• _add 함수는 기존에 node 다음에 이어져있던 n 사이에 new를 넣어 node-new-n 순서로 연결 리스트를 변형한다.
• 이중 연결리스트 방법으로 원형 데크를 풀게되면 원형의 이점을 전혀 살리지 못하여서 추천되는 방법은 아니다.

---

Question 27: k개 정렬 리스트 병합

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

입력: T = [ 1->4->5, 1->3->4, 2->6 ]

출력: 1->1->2->3->4->4->5->6

내 풀이

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if (len(lists)==0):
            return []
        
        merged_list = []
        i = 0
        for lst in lists:
            if not lst:
                i += 1
            else:
                while lst:
                    merged_list.append(lst.val)
                    lst = lst.next
                    
        if i == len(lists):
            return [] 
        else:
            merged_list.sort()
            result_node = ListNode()
            for i,num in enumerate(merged_list):
                if i == 0 :
                    result_node.val = num
                else :
                    node = result_node
                    while node.next != None:
                        node = node.next
                    node.next = ListNode(num)
            return result_node

• 연결 리스트를 리스트로 변경한 후 정렬한 다음 다시 연결 리스트로 만드는 방법을 이용하였다.

결과

타입에러가 떴다.

풀이 1: 우선순위 큐를 이용한 리스트 병합

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        root = result = ListNode(None)
        heap = []

        # 각 연결 리스트의 루트를 힙에 저장
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        # 힙 추출 이후 다음 노드는 다시 저장
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]

            result = result.next
            if result.next:
                heapq.heappush(heap, (result.next.val, idx, result.next))

        return root.next

중요 내용

1. 연결 리스트를 힙에 저장한 후 heappop() 메서드를 사용하여 작은 값 부터 추출하는 방법이다.
2. 힙에 대한 자세한 내용은 후의 15장에서 다룰 예정이므로 여기서는 우선순위 큐를 이용해 풀 수 있는 문제는 힙을 이용하는 것이 좋다 정도로 이해하자!

---

Question 28: 해시맵 디자인

put, get, remove 기능을 제공하는 해시맵을 디자인 하라

입력:
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

출력:
[null, null, null, 1, -1, null, 1, null, -1]

내 풀이

해시맵

---

풀이 1: 개별 체이닝 방식을 이용한 해시 테이블 구현

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
            
    def pop(self) -> int:
        return self.q.popleft()
        
    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0 

중요 내용

1. 파이썬에서의 큐의 구현은 데크(deque)를 이용한다.
2. 데크는 사용할 수 있는 함수가 append, popleft 이므로 이 두개의 함수를 이용해 스택을 구현해야 한다.

---

Question 24: 스택을 이용한 큐 구현

스택을 이용해 큐를 구현하라

입력: stack.push(1)

입력: stack.push(2)

입력: stack.pop()

출력: 1

내 풀이

결국 풀지 못하였다.

풀이 1: 스택 2개 사용

class MyQueue:

    def __init__(self):
        self.stack = []
        self.q = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        
    def pop(self) -> int:
        self.peek()
        return self.q.pop()
    
    def peek(self) -> int:
        if not self.q:
            while self.stack:
                self.q.append(self.stack.pop())
        return self.q[-1]

    def empty(self) -> bool:
        return (len(self.stack) + len(self.q)) == 0
            

중요 내용

1. 큐를 이용해 스택을 구현할 때의 풀이와는 다르게 pop과 append를 한번에 같이 사용하면 삭제했다가 추가하는 과정을 무한 반복하기 때문에 이 방법은 사용할 수 없다.
2. 클래스 안의 함수에서 같은 클래스 안의 다른 함수를 구현할 때 다른 함수의 return 문은 값을 반환하는데 사용된다.

---

Question 25: 원형 큐 디자인

원형 큐를 디자인하라

입력:
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(3);
myCircularQueue.enQueue(4);
myCircularQueue.Rear();

myCircularQueue.isFull();

myCircularQueue.deQueue();
myCircularQueue.isEmpty();

출력: True
True
4
False
True
False

내 풀이

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = []
        self.k = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        else:
            self.q.append(value)
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return -False
        else:
            self.q.pop(0)
            return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[0]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[-1]

    def isEmpty(self) -> bool:
        return len(self.q) == 0

    def isFull(self) -> bool:
        return len(self.q) == self.k

결과

Runtime: 85 ms, faster than 50.03% of Python3 online submissions for Design Circular Queue. Memory Usage: 14.5 MB, less than 96.23% of Python3 online submissions for Design Circular Queue

• 이 문제는 난이도가 별 두개인 것이 이해가 되지 않을 정도로 쉽게 풀었다.
• 큐의 모양이 원형이라는 특징을 살리지 않은 풀이 방법이여서 다소 변칙적인 풀이 방법이라고 할 수 있다.

---

풀이 1: 값만 변경

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): 리어 포인터 이동
    def enQueue(self, value: int) -> bool:
        if self.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False

    # deQueue(): 프론트 포인터 이동
    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self) -> int:
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]

    def isEmpty(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self) -> bool:
        return self.p1 == self.p2 and self.q[self.p1] is not None

기억해야 할 함수

1. 표현식 if 가정문 else 표현식: if, else문을 한 줄로 풀어서 쓸 수 있다.

중요 내용

1. 투 포인터 방법을 이용한 풀이 방법이다. front는 제일 앞의 값에 위치한 포인터이고, rear은 제일 뒤에 위치한 포인터이다.
2. 값을 추가하면 rear 포인터가 추가한 값으로 이동하고 값을 삭제하면 front 포인터가 삭제한 값 다음으로 넘어간다.

---