[알고리즘/자료구조] 2075 번 : N번째 큰 수 - python

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

2075번: N번째 큰 수

 

---

• 문제
• 소요시간: 22분 17초, heapq 서치 시간 포함

---

• 설계하기(접근방법) 

1. n을 입력받고 heap을 선언한다

2. 알고리즘 해석

1) 각각의 리스트를 한줄씩 입력받는다

2)각각의 원소를 순회한다.

    1: 현재 heap의 크기가 n보다 작을 경우 원소의 크기에 관계없이 heappush

    2: heap의 크기가 n 이상일 경우

           i. 만약 현재 heap의 최소값보다 현재 원소가 크다면 heappop() 후 현재 원소 push()

           ii. 만약 heap의 최소값보다 작다면 pass

3) heap의 최소값 즉, n번째 값을 출력한다.

 

 

 

 

---

• 코드(출력)

import sys
import heapq

n = int(input())

heap = []

for _ in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    for i in temp:
        if len(heap) < n:
            heapq.heappush(heap, i)
        else:
            if heap[0] < i:
                heapq.heappop(heap)
                heapq.heappush(heap, i)
            else:
                pass

print(heap[0])

---

• 얻어갈 부분

1. 이 문제의 핵심은 메모리가 제한된다는 점이다. 입력 데이터를 전부 리스트로 받는 경우 시간초과는 생기지 않지만 메모리의 초과가 발생한다. 따라서 리스트의 크기를 제한해서 입력받을 필요가 있다. 그러나 입력받을 때마다 정렬을 한다면 시간의 낭비가 발생하므로 최소값을 항상 데이터의 첫번째 인덱스로 설정하는 heap을 사용할 필요가 있다