TIL_220525_heap

https://leetcode.com/problems/kth-largest-element-in-an-array/
K번째 큰 요소

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        if biggest != cur:
            self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

import heapq



def test_maxheap_we_made(lst, k):
    maxheap = BinaryMaxHeap()

    # for 문을 눈여겨봐두세요.
    # 힙정렬 시간복잡도 계산의 토대입니다.
    for elem in lst:
        maxheap.insert(elem)

    return [maxheap.extract() for _ in range(k)][k - 1]


def test_maxheap_heapq(lst, k):
    return heapq.nlargest(k, lst)[-1]

새롭게 힙에 대한 구조와 heapq 모듈에 대한 이해를 진행함

https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
Maximum Product of Two Elements in an Array

'''

초기 생각
힙으로 안 풀면 더 쉬운 문제 같음
아까 만든 힙 구조를 가져다가 가장 큰 수 2개를 그냥 뽑아서 하면 될 것 같음...
힙을 안 쓰면 좀더 간단하게 될 것 같음
'''
from typing import List

class BinaryHeap:
    def __init__(self):
        self.item = [None]

    def __len__(self):
        return len(self.item) - 1

    def _percolate_up(self):

        cur = len(self)
        parent = cur // 2

        while parent > 0:
            if self.item[cur] > self.item[parent]:
                self.item[cur], self.item[parent] = self.item[parent], self.item[cur]

            cur = parent
            parent = cur//2

    def _percolate_down(self, cur):
        biggest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.item[left] > self.item[biggest]:
            biggest = left

        if right <= len(self) and self.item[right] > self.item[biggest]:
            biggest = right

        if cur != biggest:
            self.item[cur], self.item[biggest] = self.item[biggest], self.item[cur]
            self._percolate_down(biggest)

    def insert(self, k):
        self.item.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.item[1]
        self.item[1] = self.item[-1]
        self.item.pop()
        self._percolate_down(1)
        return root

class Solution:
    '''
    개인답안:
    그냥 간단한 방식
    최소 길이가 2니깐 2인 경우에는 그냥 2개 리턴
    2가 아니면 최대값 가져오고, 그 값을 삭제하고, 다시 최대값을 가져와서 연산해 리턴
    '''
    def maxProductMyway(self, nums: List[int]) -> int:
        if len(nums) == 2:
            return (nums[0]-1)*(nums[1]-1)

        i = max(nums)
        nums.remove(i)
        j = max(nums)
        return (i-1)*(j-1)

    '''
    힙 방식
    확실히 성능은 간단하게 하는 위가 더 괜찮음
    사람들은 문제를 어렵게 풀려 한다는 알고리즘 우승자의 말이 있었는데,
    그냥 위 방식으로 하는게 나아보임
    '''
    def maxProductMywayHeap(self, nums: List[int]) -> int:
        binaryHeap = BinaryHeap()
        for num in nums:
            binaryHeap.insert(num)
        return (binaryHeap.extract()-1)*(binaryHeap.extract()-1)

easy 단계라 간단한 문제였음
리스트와 힙 두가지 방법으로 해결함

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/
행렬에서 가장 약한 K행

'''

일단 전처리가 필요해보임
mat을 반복하면서 병사들의 수를 계산해 새로운 리스트로 반환,
이후 새로 반환한 리스트의 인덱스와 값을 이용해 최소값(min 함수를 사용)을 비교하면서
새롭게 리스트를 반환하면 될 것 같음

'''
import collections
import heapq
from typing import List

class MyHeap:
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) -1

    def _percolate_up(self):
        cur = len(self)
        parent = cur //2

        while parent > 0:
            if self.items[cur] > self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

class Solution:
    '''
    개인 답안
    힙은 사용 안하고 리스트에 내용을 합쳐서 나온 군인의 수를 딕셔너리로 넣음
    완성된 딕셔너리는 람다를 이용해 펼쳐준 뒤, sorted함수를 통해 값을 기준으로 정렬해줌
    정렬을 값을 기준으로 하지만 반환되는 것은 키가 반환 됨
    '''
    def kWeakestRowsMyway(self, mat: List[List[int]], k: int) -> List[int]:

        soldiers_dict = collections.defaultdict()
        for idx, mt in enumerate(mat):
            count = sum(mt)
            soldiers_dict[idx] = count
        resulte = sorted(soldiers_dict, key = lambda x: soldiers_dict[x])

        return resulte[:k]

힙이 아닌 딕셔너리를 썻지만, 간단하게 문제를 푸는게 가장 좋은 방법 같음

https://www.acmicpc.net/problem/1927
최소 힙

https://www.acmicpc.net/problem/11279
최대 힙

# 최소 힙

import heapq

n = int(input())
heap = []
for _ in range(n):
    target = int(input())
    if target == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, target)


# 최대 힙

import heapq
import sys

input = sys.stdin.readline
n = int(input())
heap = []
for _ in range(n):
    target = -int(input())
    if target == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, target)

처음으로 짝 프로그래밍으로 진행 한 알고리즘임
역시나 같이 진행하니 빠르고 몰입이 가능했음
시간 낭비가 없고 몰입이 가능했다는 점만 하더라도 장점이 많음

오늘 타 기수가 실전 프로젝트로 만든 마피양을 체험 플레이 해봤음
도트를 이용해 깔끔한 디자인이 됨
디자인에서 신문 식으로 나오는게 조금 난잡했음
나도 도트를 이용해 깔끔한 디자인을 만들면 좋을 것 같음
평소에 도트 열심히 연습해야겠음