백준 2075번 N번째 큰 수

슬라이딩 윈도우 방식으로 풀이해보려 하였으나, 생각해 보니 우선순위 큐를 이용해서 접근하는 것이 거의 유사한 방법론으로 보여서 시도하였다.

슬라이딩 윈도우 (최댓값 찾기 예시)

• 0행과 1행의 정보를 비교하여 최댓값을 저장한다.
• 이후에는 그 결과와 2행의 정보를 비교하면서 예전에 탐색했던 0행의 정보를 다시 들춰보지 않도록 "창문" 형태로 구간을 이동시킨다.

처음 로직은 heap의 크기를 5로 유지하면서, 가장 큰 수보다 더 큰 수가 탐색되었을 때 heap에 밀어넣어 주는 방식이었다.

메모리를 줄이는 것이 관건이었는데, 주어진 표를 저장하면 4byte * (N x N) 이고, 최대 N이 1500이므로 공간복잡도는

약 9MB를 차지하여, 충분하다고 보았다. 하지만 여기서 메모리 초과가 발생하게 되는데,,
pypy로 시도하면 돌아가긴 하나 index error가 발생했다.

아무래도 python3로 채점 시 기본적으로 차지하는 메모리 공간이 존재하는 듯하다. (라이브러리 탓인지도 모르겠다)

import sys
import heapq

N = int(sys.stdin.readline())
table = []

for _ in range(N):
    table.append(list(map(int, sys.stdin.readline().split())))

maxi = table[0][0]
heap = []
for i in range(N):
    for j in range(N):
        if table[i][j] > maxi:
            heapq.heappush(heap, table[i][j])
        if len(heap) > N:
            heapq.heappop(heap)


print(heap[0])

pypy에서 무엇이 문제였을고 하니 N이 1일 경우에, 그러니까 maxi가 정답 자체일 경우에 heap에 아무것도 저장되지 않기 때문에 마지막 print가 index error를 마주치는 것이었다..!

하여 아래와 같이 수정하였다. (table도 바로바로 받는 형태로 구성했다)

import sys
import heapq

N = int(sys.stdin.readline())
heap = []

for _ in range(N):
    table = list(map(int, sys.stdin.readline().split()))

    for item in table:
        heapq.heappush(heap, item)
        if len(heap) > N:
            heapq.heappop(heap)

print(heap[0])

이리하여 통과가 되었고, 상위권 정답코드를 보니 훨씬 깔끔하다.
다소 원초적인 방법일 수 있으나, table에 첫 행을 저장해 두고 다음 행을 table 뒤에 붙인 뒤 역순 정렬하여 가장 큰 5개의 수만 남겨두는 형태이다. 이게 되네? 느낌

import sys

N = int(sys.stdin.readline())
table = list(map(int, sys.stdin.readline().split()))

for _ in range(N - 1):
    table += list(map(int, sys.stdin.readline().split()))
    table = sorted(table, reverse=True)[:N]

print(table[N-1])

TIL

매 행을 계속 비교하게 되면 자칫 $O(N^2)$의 시간복잡도를 가질 수 있는 것을 우선순위큐를 이용해서 $Nlog(N)$의 시간복잡도로 개선할 수 있음을 배웠다. 다만, 의외로 간단하게 생각하면 더 쉽고 빠른 알고리즘을 고안할 수 있을 것 같다. 붙이고 자르는 방식이라니... 상상조차 못했다.