항해99 알고리즘 10회차

최대 힙 자료구조

• 삭제를 한번 더 하면은 루트값이 정상이 아니였다.
• 조건문 추가 해주니까 정상적으로 작동 하는 것 같다.
• 왼쪽 오른쪽도 비교해서 제일 큰값이랑 스왑을 해야지 삭제 처리가 제대로 된다

# 최대 힙
class Heap:

    def __init__(self, nums=[]):
        self.nums = [None] + nums

    def heap_up_sort(self):
        # 현재 위치
        cur = len(self.nums) - 1
        # 부모노드 위치
        parent = cur // 2

        while parent > 0:
            # 현재값이 부모보다 클 경우, 스왑
            if self.nums[cur] > self.nums[parent]:
                self.nums[cur], self.nums[parent] = self.nums[parent], self.nums[cur]

            # 현재값을 부모로 올라감
            cur = parent

            # 부모노드 위치
            parent = cur // 2

    def heap_down_sort(self, cur):

        # 왼쪽이나 오른쪽이 더 클 경우 스왑.
        # 0번부터 내려가야함
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self.nums)-1 and self.nums[cur] < self.nums[left] and self.nums[left] > self.nums[right]:
            biggest = left

        if right <= len(self.nums)-1 and self.nums[cur] < self.nums[right] and self.nums[left] < self.nums[right]:
            biggest = right

        if biggest != cur:
            self.nums[cur], self.nums[biggest] = self.nums[biggest], self.nums[cur]
            self.heap_down_sort(biggest)

    def insert(self, n):
        self.nums.append(n)
        self.heap_up_sort()

    def remove(self):
        if not self.nums:
            return None

        root = self.nums[1]
        self.nums[1] = self.nums[-1]
        self.nums.pop()
        self.heap_down_sort(1)
        return root


# 세팅 된 최대힙 배열
test = Heap([8, 6, 3, 4, 1, 2])
test.insert(9)
test.insert(5)
test.insert(7)
test.remove()
test.remove()
print()

---

Kth Largest Element in an Array - LeetCode

문제 접근 🤔

힙을 직접 구현한뒤에 파이썬 힙 라이브러리를 사용 하였는데

• 파이썬 힙 라이브러리가 사용을 하면은 최소값, 최대값 순서대로 뽑을 수가 있었다.
• heapq.nlargest(k, lst)를 사용하면 lst에 배열을 힙 순서대로 정렬을 하고 큰 값 부터 k만큼 배열에 담아서 반환해준다.
  • k가 배열의 인덱스가 초과해도 에러가 안뜬다?

놓쳤던 부분 😅

• 힙을 직접 구현한다고 시간 다 보냈다.

코드 😁

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

---

Maximum Product of Two Elements in an Array - LeetCode

문제 접근 🤔

• 제일 큰 값 2개를 -1을 한 후 곱해주면 될 것 같다.

놓쳤던 부분 😅

• 없음

코드 😁

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        lst = heapq.nlargest(2, nums)
        return (lst[0]-1) * (lst[1]-1)

---

Maximum Product of Two Elements in an Array - LeetCode

문제 접근 🤔

• 솔져를 Row 개수 마다 체크
• 솔져가 많은 로우 일 수록 뒤로 가야한다.
• 최소힙을 사용하여 k번으로 약한 솔져 배열을 준다.

놓쳤던 부분 😅

• 파이썬 문법이 아직 안친하다.

코드 😁

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        min_heap = []
        for index in range(len(mat)):
            soldiers_count = 0

            for soldier in mat[index]:
                if soldier == 1:
                    soldiers_count += 1

            # 힙에 개수, 인덱스값 추가
            heapq.heappush(min_heap, (soldiers_count, index))

        result = [i[1] for i in heapq.nsmallest(k, min_heap)]
        return result

---

1927번: 최소 힙

문제 접근 🤔

• 최소힙을 사용해서 적은 값 부터 출력

놓쳤던 부분 😅

• 첫 번째 코드
  • 시간 초과로 실패를 하였는데 스택에 값을 쌓고 최소힙으로 값을 출력 후 스택에서 삭제를 해서 O(n)이 돼서 실패 같다.
• 두 번째 코드
  • 힙을 스택 처럼 사용해서 당연히 속도에 문제가 생겼었고
  • 힙으로 push, pop하면 되는 단순한 문제였다.

코드 😁

• 첫 번째 코드 - 실패

import heapq
import sys

heap = []
num_count = int(sys.stdin.readline())
for _ in range(num_count):
    num = int(sys.stdin.readline())
    # 힙이 없는데 출력 할 경우
    if not heap and num == 0:
        print(0)
        continue

    # 0 이상 이면 값을 추가
    if num > 0:
        heap.append(num)

    # 힙이 있으면 출력
    if heap and num == 0:
        x = heapq.nsmallest(1, heap)[0]
        print(x)
        heap.remove(x)

• 두 번째 코드 - 성공

import heapq
import sys

heap = []
num_count = int(sys.stdin.readline())
for _ in range(num_count):
    num = int(sys.stdin.readline())
    # 힙이 없는데 출력 할 경우
    if not heap and num == 0:
        print(0)
        continue

    # 0 이상 이면 값을 추가
    if num > 0:
        heapq.heappush(heap, num)

    # 힙이 있으면 출력
    if heap and num == 0:
        print(heapq.heappop(heap))

---

11279번: 최대 힙

문제 접근 🤔

• 최소힙과 완전 같지만 최대힙으로만 방향을 바꾸면 됐다.

놓쳤던 부분 😅

• 최소힙을 최대힙으로 어떻게 바꾸지 생각하였는데
• 음수로 값을 넣으면 역으로 최대힙이 된다.

코드 😁

import heapq
import sys

heap = []
num_count = int(sys.stdin.readline())
for _ in range(num_count):
    num = int(sys.stdin.readline())
    # 힙이 없는데 출력 할 경우
    if not heap and num == 0:
        print(0)
        continue

    # 0 이상 이면 값을 추가
    if num > 0:
        heapq.heappush(heap, -num)

    # 힙이 있으면 출력
    if heap and num == 0:
        print(-heapq.heappop(heap))