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

2075번: N번째 큰 수

해당문제는 메모리를 최적화 해야하는 문제입니다.

시간복잡도는 O(N^2)으로 풀 수 있고, 메모리는 12MB로 작게 주어졌습니다.

따라서 우리가 흔히 사용하는 모든 원소를 다 넣고, 정렬을 하는 방식으로는 풀 수 없습니다.

이러한 문제를 해결하기위하여 우선순위 큐 자료구조를 사용하여 항시 큐의 첫번째 인덱스가 N번째 큰값임을 보장해야합니다.

기존 해결방식 ( O(N^) )

from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
priorty = [deque() for _ in range(N)]

for _ in range(N):
    temp = list(map(int, input().split()))
    for i in range(N):
        priorty[i].append(temp[i])

cnt = 0
for _ in range(N+1):
    nums = []
    idx = 0
    maxvalue = 0
    for i in range(N):
        if priorty[i]:
            idx = i
            maxvalue = priorty[i][-1]
            break

    cnt += 1
    for i in range(1, N):
        if priorty[i][-1] > maxvalue:
            maxvalue = priorty[i][-1]
            idx = i

    num = priorty[idx].pop()
    if cnt == N:
        print(num)
        break

우선순위 큐를 사용한 로직 ( O(N^) ) 큐의 사이즈는 항상 N을 보장합니다.

import heapq
import sys
input = sys.stdin.readline
N = int(input())
queue = []

for i in range(N):
    temp = list(map(int, input().split()))
    if i == 0:
        for num in temp:
            heapq.heappush(queue, num)
    else:
        for num in temp:
            if num > queue[0]:
                heapq.heappush(queue, num)
                heapq.heappop(queue)

print(queue[0])