최대 힙 자료구조
- 삭제를 한번 더 하면은 루트값이 정상이 아니였다.
- 조건문 추가 해주니까 정상적으로 작동 하는 것 같다.
- 왼쪽 오른쪽도 비교해서 제일 큰값이랑 스왑을 해야지 삭제 처리가 제대로 된다
# 최대 힙
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
Can you solve this real interview question? Kth Largest Element in an Array - Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct eleme
leetcode.com
문제 접근 🤔
힙을 직접 구현한뒤에 파이썬 힙 라이브러리를 사용 하였는데
- 파이썬 힙 라이브러리가 사용을 하면은 최소값, 최대값 순서대로 뽑을 수가 있었다.
- 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
Can you solve this real interview question? Maximum Product of Two Elements in an Array - Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1). Example 1: Inpu
leetcode.com
문제 접근 🤔
- 제일 큰 값 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
Can you solve this real interview question? Maximum Product of Two Elements in an Array - Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1). Example 1: Inpu
leetcode.com
문제 접근 🤔
- 솔져를 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번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
문제 접근 🤔
- 최소힙을 사용해서 적은 값 부터 출력
놓쳤던 부분 😅
- 첫 번째 코드
- 시간 초과로 실패를 하였는데 스택에 값을 쌓고 최소힙으로 값을 출력 후 스택에서 삭제를 해서 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번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
문제 접근 🤔
- 최소힙과 완전 같지만 최대힙으로만 방향을 바꾸면 됐다.
놓쳤던 부분 😅
- 최소힙을 최대힙으로 어떻게 바꾸지 생각하였는데
- 음수로 값을 넣으면 역으로 최대힙이 된다.
코드 😁
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))
'항해99' 카테고리의 다른 글
항해99 알고리즘 12회차 (0) | 2023.12.26 |
---|---|
항해99 알고리즘 11회차 (0) | 2023.12.25 |
항해99 알고리즘 9회차 (0) | 2023.12.21 |
항해99 알고리즘 8회차 (0) | 2023.12.19 |
항해99 알고리즘 7회차 (0) | 2023.12.19 |