[백준/2075/파이썬] N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

조건

• NxN의 표에 수 N^2가 채워져있다. 채워진 수에는 한가지 특징이 있는데, 모든 수는 자신의 한칸 위에 있는 수보다 크다는 것이다.

우선, 처음 든 생각은 N번째 큰 수를 구하려면, 난 priority queue를 사용해야겠다 . 라는 생각이 빡 들었음. 우선순위 큐는 N번쨰 큰 수를 구할 수 있다고 알고 있었음.

SOL

1.MAX Heap에 다 넣고, n-1번 뽑으면 , 그게 n번쨰 큰 수아닌가?

• Python에서 MAX_Heap을 만드는 방법
  • 음수는 절대값이 클수록, 작다.
  • 양수는 절대값이 클수록, 크다.
  이 두 사실을 이용해서, min_heap → max_heap으로 만들어 줄 수 있다.여기서, 이 값을 최소힙에 넣어주면, [-9,-7,-6,-1,1] 로 들어가게 된다.

  #코드로 표현하자면 이렇게됨.
  import heapq
  
  arr=[-1,6,7,9,1]
  max_heap=[]
  
  for num in arr:
  	heapq.heappush(max_heap,(-num,num))
  while max_heap:
  	print(heapq.heappop(max_heap)[1])
  

• 따라서, heap에 넣어줄때, 부호를 바꾼 값과, 원래의 값을 같이 넣어주면 된다.
• arr=[-1,6,7,9,1] 이라고 했을때, arr의 부호가 바뀐 값은 [1,-6,-7,-9,-1] 이다.

2. 히프가 비어있으면, 히프에 넣고 아니면, 히프의 root(최솟값)보다 입력값이 크면 해당 값을 넣어주고, 히프에서 1개를 빼준다. =⇒ 즉, 상위 N개에 대한 최소힙을 만들어주는 느낌. 그럼 상위 N개에 대해 최소힙의 root는 N번째 큰수가 되버리는거 니까!

 

1번을 처음에 해줬는데, 구글링 해보니까 2번 방법이 정답이라고 합니다. ( 1번은 메모리초과가 발생)

import heapq
import sys
input = sys.stdin.readline

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

for _ in range(n):
	numbers = list(map(int,input().rstrip().split()))
	
	if not heap:
		for num in numbers:
			heapq.heappush(heap,num)
	else:
		for num in numbers:
			if heap[0]<num:
				heapq.heappush(heap,num)
				heapq.heappop(heap)
print(heap[0])

#요런느낌!