[heap/백준] 2075번 : N번째 큰 수

- 문제 : https://www.acmicpc.net/problem/2075

 

문제 이해 

문제 자체를 이해하는 데는 그렇게 어렵지 않았다. 주어진 N^2개의 수 중에서 N번째 수를 구하면 된다. 

그런데 N이 최대 1500이므로 N^2개의 원소를 하나의 배열에 모으고, 그걸 정렬하는데는 O(N^2)의 시간 복잡도가 발생한다. 그래서 다른 방법으로 진행해야하는데 이 때 힌트가 될만한 게, 하나의 열에서는 크기 순서대로 행이 정렬되었다는 것이다. 따라서 시간 복잡도 + 같은 열에서는 원소 오름차순 정렬 이라는 조건으로 heap을 사용해 문제를 해결할 수 있다. 

여기에서 heap을 사용하는 대상이 주어진 배열이 아니라, heap이라는 새로운 배열을 heap으로 진행해야한다. 

 

풀이 로직

- heap이라는 배열을 heap으로 적용하는데, heap 배열의 길이는 최대 N개가 될 수 있다. 

- 먼저 주어진 값을 temp로 받은 뒤 각 temp의 각 원소(each)를 탐색하는데 len(heap)의 값에 따라 다르게 진행한다.

1. len(heap) < n 인 경우는 each를 heap에 그냥 넣는다.

2. len(heap) >= n 인 경우는 heap의 첫 번째 원소는 배열의 최솟값이므로 만약 each > heap[0] 이라면 heappop()을 한 뒤 each 값을 넣는다 

- 반복문을 끝낸 뒤 heap에 남은 값들은 주어진 수를 정렬했을 때 heap[0] 값이 전체에서 n번째 수이므로 heap[0]을 출력한다.

 

정답풀이 

import heapq

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

for _ in range(n):
    temp = map(int, input().split())
    for each in temp:
        if len(heap) < n:
            heapq.heappush(heap, each)
        else:
            if heap[0] < each:
                heapq.heappop(heap)
                heapq.heappush(heap, each)
                
print(heap[0])

 

 

참고 블로그 

[BOJ] 2075 N번째 큰 수