2075 힙큐 - 우선순위 큐

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

출력

첫째 줄에 N번째 큰 수를 출력한다.

35

문제 풀어보기

첫번째 시도 -구현 성공, 그러나 공간복잡도 해결 못함

from heapq import heappop,heapify

x = int(input())

x_list = []

for i in range(x):
    t_list = [(int(j)*-1) for j in input().split(" ")]
    x_list.extend(t_list)

heapify(x_list)

temp = 0
for i in range(x):
    temp = heappop(x_list)

print(temp * -1)

🚩 파이썬의 공간 복잡도

파이썬은 리스트가 동적인메모리를 가져서 리스트의 범위를 넘어서 추가할 때마다 공간복잡도가 올라가 메모리가 낭비된다.

그래서 배열의 크기를 고정적으로 만들어야한다.

for i in range(x):
    a_list = list(map(int, input().split(" ")))
    for i in a_list:
        if len(x_list) < x:
            heappush(x_list,i)
        else:
            temp = heappop(x_list)
            if  temp < i:
                heappush(x_list,i)
            else:
                heappush(x_list,temp)

→ x_list의 크기를 x로 제한을 두어서 공간복잡도를 해결할 수 있다.

정답코드

이진 힙의 루트는 항상 트리내에서 작다는 것을 활용했다.

n번째로 큰 수를 출력해야할 때, 이진 힙에 제일 큰 수 1번째부터 n번째로 큰 수까지 넣은 후, 가장 작은 루트 값을 출력하도록 했다.

만약에 n크기를 가지는 힙이 꽉 차있다면, 루트는 힙 내에서 가장 작다. 즉, 이 힙내에서 만큼은 루트는 이미 n번째로 크다.

• 새로이 추가할 값이 루트보다 작다는 것은 이미 추가할 값이 전체 값에서 n번째 이후 순서를 가진 다는 것이다.
• 새로이 추가할 값이 루트보다 크다는 것은 추가할 값이 전체 값에서 n번째 내로 클 수 있다는 것이다.

from  heapq import heappop,heapify,heappush

x = int(input())

x_list = []
heapify(x_list)

for i in range(x):
    a_list = list(map(int, input().split(" ")))
    for i in a_list:
        if len(x_list) < x:
            heappush(x_list,i)
        else:
            temp = heappop(x_list)
            if  temp < i:
                heappush(x_list,i)
            else:
                heappush(x_list,temp)

print(heappop(x_list))