[BOJ] 2075 N번째 큰 수 - Python

문제

---

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

2075번: N번째 큰 수

 

풀이

---

N번째 큰 수 시간 제한과 메모리 제한

해당 문제는 N의 최대 크기가 1500으로 시간 제한만 고려한다면 입력되는 숫자 모두를 받아서 정렬하는 방식을 사용해도 풀이가 가능합니다. 하지만 메모리 제한으로 인해 위와 같은 풀이를 제출 시 메모리 초과가 납니다.

 

따라서 N^2 개의 숫자 모두를 배열에 저장하고 그 후에 문제 조건에 따라 무언가를 처리하는 방식으로는 해당 문제를 풀기 어렵습니다.

 

이에 N^2의 숫자들을 모두 살펴보면서 로직을 수행하되 이러한 입력들을 크기가 N 짜리 우선순위 큐에서 처리해주면 문제를 해결할 수 있습니다.

 

주요 로직은 아래와 같습니다.

현재 확인하고 있는 숫자에 대해서,, ( N^2의 숫자를 하나하나 확인함)

1. 우선순위 큐 안에 들어있는 원소의 개수가 N개 미만이라면
    ➜ 우선순위 큐에 집어넣는다.

2. 우선순위 큐 안에 들어있는 원소의 개수가 N개라면
    1) 현재 확인하고 있는 숫자가 우선순위 큐의 최솟값보다 작은 경우
        ➜ 무시한다.
    2) 그 외의 경우
        ➜ 우선순위 큐의 최솟값을 제거하고 현재 확인하고 있는 숫자를 우선순위 큐에 삽입한다.

 

풀이 코드는 아래와 같습니다.

import heapq

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

for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
        else:
            if heap[0] < number:
                heapq.heappop(heap)
                heapq.heappush(heap, number)
print(heap[0])