[백준][2075][우선순위큐] N번째 큰 수 python (211030)

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

2075번: N번째 큰 수

이해도

★★☆☆☆

접근법

• 반복문 접근하면 메모리 초과가 나서 우선순위 큐를 구현해야 한다.
• 우선순위 큐는 힙으로 구현한다.
• 한 행씩 진행한다.
• 힙이 비어있다면 푸시하고, 비어있지 않은데 가장 작은 수보다 큰 수가 나오면 푸시하고, 추가된 힙에서 가장 작은 수를 pop 한다.
• 하나씩 추가했다 뺏다를 반복하므로 가장 큰 수부터 N개의 숫자가 힙에 담겨있다.
• 그 중 가장 작은 수를 출력한다.

왜 메모리 초과 문제가 발생하지 않는지?

• 우선순위 큐의 시간복잡도(힙의 데이터 삽입과 삭제)는 logN이다.
• 반복문의 경우 이중 for 문 뿐 아니라 배열을 전체순회하므로 우선순위 큐보다 시간복잡도가 높다.

import heapq

N = int(input())

heap = []
for _ in range(N):
    nums = list(map(int, input().split()))
    # 만약 heap 이 비어있다면 item을 heap으로 푸시한다.
    if not heap:
        for num in nums:
            heapq.heappush(heap, num)
    # heap 이 비어있지 않다면
    else:
        for num in nums:
            # 만약 가장 작은 항목보다 큰 수가 나오면 해당 수를 푸시하고, 새로운 힙에서 가장 작은 수를 pop 한다.
            if heap[0] < num:
                heapq.heappush(heap, num)
                heapq.heappop(heap)

# 반복을 마치면 큰 수부터 N개가 힙에 담겨 있으므로, 그 중 가장 작은 수를 반환한다.
print(heap[0])

코드 참고

[백준/2075번/파이썬(Python)] N번째 큰 수 / 우선순위 큐

 

메모리 초과한 반복문

# 메모리 초과

N = int(input())
board = [list(map(int, input().split())) for x in range(N)]


maxnum = 0
for i in range(N):
    for j in range(N):
        maxnum = max(board[i][j], maxnum)

arr = []
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        arr.append(maxnum - board[i][j])
        arr.sort()

print(maxnum - arr[N-1])