N번째 큰 수[백준 2075번] - python

정답코드 먼저 살펴보자

 

import sys, heapq

def BOJ2075(): 
  n = int(input())
  array = list(map(int, sys.stdin.readline().split()))
  for _ in range(n-1) :
    for i in list(map(int, sys.stdin.readline().split())):
      if array[0] < i :
        heapq.heappop(array)
        heapq.heappush(array, i)
    
  print(array[0])

BOJ2075()

 

맨 처음에는 배열로 입력받지 않고 배열에 값을 하나씩 넣은다음에 전체를 정렬후 값을 출력했었다.

문제의 조건은 12mb이다.

메모리 초과로 바로 실패했다.

 

쉽사리 방법을 떠올리지 못했고 다른 분들의 블로그를 참고했다.

 

접근 방법

1. 우선순위 큐를 이용하자.

2. 우선순위 큐의 크기를 n으로 지정

3. 입력받는 값이 큐의 최솟값보다 크면 큐에 계속 넣어준다.

4. 큐의 크기는 n이다. 따라서 마지막에 큐에 남은 첫번째 인덱스 값은 n번째로 큰 수이다.

 

 

 

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

2075번: N번째 큰 수