백준 2075 N번째 큰 수 / python

문제 : 2075

풀이 point

입력 받은 배열에서 N번째 큰 수를 찾는 문제이다. 그저 배열을 탐색하면 되지 않나? 라는 생각이 들 수 있지만, 문제 조건을 자세히 보면 메모리 크기가 12MB 제한이므로 1500x1500 배열을 만들어 값을 저장하기에는 부족하다. 때문에 행마다 한번씩 볼 수 있을 정도이다. 다만 이러면 그 전 값을 알 수 없어 N번째 큰수를 알 수 없다.

해결책은 우선순위 큐이다.

풀이 방법

우선 한 행을 입력으로 받는다.
그 다음 우선순위 큐에 하나씩 그 값들을 넣는다. 이때 N번째 큰수를 구하는 것이기 때문에 길이는 N만 있으면 되기에 넣기 전에 길이를 검사한다.

만약 길이가 N보다 작다면 그냥 넣고, N이라면 하나를 제거하고 넣어야 한다. 이때 우선순위 큐의 첫번째 값(최소힙이라서 우선순위 큐 안의 원소 중 가장 작은 값이다)과 현재 숫자를 비교한다. n이 더 크다면 첫번째 값을 큐에서 제거한 후 현재 값을 넣어준다.

왜 저런 과정을 거칠까?

현재 우선순위 큐는 최소힙이기 때문에 가장 작은 값을 기준으로 있다.
예를들면, 5번째 큰수를 구하기 위해 총 5개의 우선순위 큐 원소들이 있다고 가정하자.

ex)
5 4 3 2 1

여기서 6이 들어왔다면 가장 작은 수인 1보다 크므로 1을 제거하고 6을 집어넣는다.
그러면 우선순위 큐 원소는 6 5 4 3 2가 되며 5번째 큰 수는 2가 된다.

풀이 코드

import heapq

pq = []
N = int(input())

for i in range(N):
  nums = list(map(int, input().split()))

  for n in nums:
    if len(pq) < N:
      heapq.heappush(pq, n)
    else:
      if pq[0] < n:
        heapq.heappop(pq)
        heapq.heappush(pq, n)

print(pq[0])