[Algorithm] 백준 2075 - N번째 큰 수 in Python(파이썬)

💡 백준 2075:

큐 기본 구조 활용 및 우선순위큐 이해

🌱 코드 in Python

알고리즘: Queue

이 문제를 보자마자 이거 걍 max_heap 구조로 만들어서 n번째 값 뽑으면 되는거 아니야? 하고

import sys, heapq

input = sys.stdin.readline
n = int(input())
q = []
for i in range(n):
	num_list = list(map(int, input().split()))
	for j in num_list:
		heapq.heappush(q, -j)
for i in range(n - 1):
	heapq.heappop(q)
print(-q[0])

위와 같이 만들었다가 메모리 초과 낭패를 봤다 ^^!
그래.. 이렇게 쉬울리 없지.. ㅠㅠ

위 코드는 그냥 들어오는 입력값에 대해 일단 q에 min_heap 구조로 때려넣었다가,
n - 1번째까지 q를 빼고 n번째 큰 수가 되었을 경우 print하도록 했다
그치만,, 어쨌든 메모리초과니깐,, ㅠ 다시 짰다

import sys, heapq

input = sys.stdin.readline
n = int(input())
q = []
for i in range(n):
	num_list = list(map(int, input().split()))
	if not q: # q에 아무것도 없는 첫번째 입력 시
		for num in num_list:
			heapq.heappush(q, num) # min_heap 구조로 q 채우기
	else:
		for num in num_list: # q에 값이 있을 시 늘 q의 길이를 n으로 유지하기
			if q[0] < num: # q 최솟값보다 현재 숫자가 클 경우 n번째로 큰 수가 바뀌어야 하기 때문에
				heapq.heappush(q, num) # 현재 숫자를 push 하고
				heapq.heappop(q) # 기존 최솟값 pop
print(q[0])

다음 방법으로 메모리 초과를 방지하기 위해서 q 길이를 계속 n만큼 유지하는 방법을 택했다
일단 첫번째 입력값을 q에 min_heap 구조로 때려넣고
그 다음부터 입력값에 대해서 q의 최솟값보다 큰 수가 들어오면 q 원소를 교체하는 식으로 하면

결국 q배열엔 가장 큰 n개의 수만 남고 q 구조 자체가 min_heap 구조 이기 때문에
q의 첫번째 요소가 n번째로 큰 수가 된다

🧠 기억하자

1. 메모리.. 메모리 계산을 하자.. 조건을 잘 이해하자..
   • 메모리 크기 계산 잘 생각해봐야지 엉엉 ㅠ
2. 사람들은 참 잘도 방법을 생각한다 대단해
   • 크기 유지! 미니힙 유지! n번째로 큰 수는 다시 말해 가장 큰 수 n개중 가장 작은 수라는 것!
3. 리스트에 원소가 존재할 때 if list로 조건을 검사할 수 있는데, 반대의 경우 if !list가 안되길래 어떻게 써야하지 하고 찾아보니 if not list였다!

백준 2075 바로가기