코딩테스트 불길한 수열 문제
문제
4, 13, 413, 134와 같이 숫자가 13과 4를 이용해서 만들 수 있는 수를 불길한 수라고 한다. 그리고 불길한 수가 오름차순으로 나열된 수열을 불길한 수열이라고 한다. 예를 들어 불길한 수열은 다음과 같이 나열될 수 있다.
ex) S = {4, 13, 44, 134, 413, 444, 1313......}
n이 매개변수로 주어질 때, 불길한 수열에서 n번째 불길한 수를 구하시오.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | from heapq import heappush, heappop, heapify def solution2(n): q = [4,13] heapify(q) while n: n-=1 v=heappop(q) heappush(q,v*10+4) heappush(q,v*100+13) return v print(solution2(100)) | cs |
최소 힙 생성
heap = []
from heapq import heappush
heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
print(heap)
[1, 3, 7, 4]
힙에서 원소 삭제
from heapq import heappop
print(heappop(heap))
print(heap)
1
[3, 4, 7]
기존 리스트를 힙으로 변환
from heapq import heapify
heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)
[1, 3, 5, 4, 8, 7]
nums = [4, 1, 7, 3, 8, 5]
heap = nums[:]
heapify(heap)
print(nums)
print(heap)
[4, 1, 7, 3, 8, 5]
[1, 3, 5, 4, 8, 7]
최대 힙
from heapq import heappush, heappop
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heappush(heap, (-num, num)) # (우선 순위, 값)
while heap:
print(heappop(heap)[1]) # index 1
8
7
5
4
3
1
from heapq import heappush, heappop
def nth_smallest(nums, n):
heap = []
for num in nums:
heappush(heap, num)
nth_min = None
for _ in range(n):
nth_min = heappop(heap)
return nth_min
print(nth_smallest([4, 1, 7, 3, 8, 5], 3))
4
from heapq import nsmallest
nsmallest(3, [4, 1, 7, 3, 8, 5])[-1]
from heapq import nlargest
nlargest(3, [4, 1, 7, 3, 8, 5])[-1]