1927 최소 힙, 1715 카드 정렬하기, 1766 문제집

1927 최소 힙, 1715 카드 정렬하기, 1766 문제집

1927 최소 힙

# 첫번째 풀이(힙 이용하지 않음. 시간초과)
n = int(input())
array = []
zero = 0
count = 0
for _ in range(n):
	num = int(input())
	if num == 0:
		if count == 0:
			print(0)
		else:
			array = sorted(array, reverse=True)
			print(array[-1])
			array = array[:-1]
			count -= 1
	else:
		array.append(num)
		count += 1
        
# 두번째 풀이(힙 이용)
import heapq

n = int(input())
heap = []
result = []

for _ in range(n):
	data = int(input())
	if data == 0:
		if heap:
			result.append(heapq.heappop(heap))
		else:
			result.append(0)
	else:
		heapq.heappush(heap, data)
		
for data in result:
	print(data)

- 가장 작은 값을 빼올 때 힙 사용

- 힙 라이브러리 사용 : import heapq,  heapq.heappop(list), heapq.heappush(list)

 

 

1715 카드 정렬하기

# 첫번째 풀이(메모리 초과)
def sumside(array): # 재귀 함수 이용
	cards= 0
	if len(array) == 1:
		cards += array[0]
		return cards
	elif len(array) == 0:
		return cards
	else:
		return ((array[0] + array[1]) * 2) + sumside(array[2:])
n = int(input())
array = []

for _ in range(n):
	array.append(int(input()))
	
array = sorted(array)
print(sumside(array))

# 두번째 풀이(힙 사용)
import heapq

n = int(input())
heap = []
for _ in range(n):
	data = int(input())
	heapq.heappush(heap, data)

result = 0
while len(heap) != 1:
	one = heapq.heappop(heap)
	two = heapq.heappop(heap)
	sum_val = one + two
	result += sum_val
	heapq.heappush(heap, sum_val)
	
print(result)

- 뺀걸 조합해서 다시 넣고 활용하는 법도 있음

 

 

1766 문제집

import heapq

n, m = map(int, input().split())
array = [[] for i in range(n+1)]
indegree = [0] * (n+1)

for _ in range(m):
	x, y = map(int, input().split())
	array[x].append(y)
	indegree[y] += 1

heap = []
result = []

for i in range(1, n+1):
	if indegree[i] == 0:
		heapq.heappush(heap, i)
		
while heap:
	data = heapq.heappop(heap)
	result.append(data)
	for y in array[data]:
		indegree[y] -= 1
		if indegree[y] == 0:
			heapq.heappush(heap, y)
			
for i in result:
	print(i, end=' ')

- 위상 정렬을 이용.(반복 학습 필요. 문제에 적용하기 어려웠음)

- list comprehension 이용하는 습관 들이기

- list * int값 이용해서 길이 리스트 길이 늘이기

- print(i, end= ' ')이용해서 한 칸 띄워서 한 줄에 출력