[BOJ] 2075번 - N번째 큰 수

문제

2075번: N번째 큰 수

 

🚦 문제 유형

• 자료 구조
• 정렬
• 우선순위 큐

 

✏️ Solution

파이썬의 heapq 라이브러리를 사용하여 우선순위 큐를 통해 문제를 풀 수 있다.

N이 최대 1500이고 최대 2,250,000개의 값을 가질 수 있는데, 그 중 N번째 큰 수를 찾기위해 순차탐색을 하는 것은 시간초과가 뜰 것이다.

최댓값 또는 최솟값을 찾을 때 힙 자료구조를 활용하면 쉽게 구할 수 있다. 

N번째 큰 수를 찾는 방법은 모든 원소를 힙에 넣고 max_heap 구조에서 N번 heapq.heappop()을 하면 될 것이다.

하지만, 이 풀이방법은 정답은 출력하지만 메모리 초과가 발생한다.

따라서 메모리초과를 해결할 수 있는 다른 방법을 생각해야 했다.

메모리 초과 코드는 다음과 같다.

# 메모리 초과
import sys
import heapq

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

for _ in range(N):
    tmp = list(map(int, sys.stdin.readline().strip().split(' ')))
    for i in tmp:
        heapq.heappush(table, (-i, i))

for _ in range(N):
    N_max = heapq.heappop(table)

print(N_max[1])

파이썬 메모리 초과에 대한 이유를 몇 가지 찾아봤는데 다음과 같은 이유가 있었다.

1. 스택 오버플로우
2. 배열에 너무 많은 변수를 저장해서
3. DFS 같은 재귀 호출을 너무 많이해서

아마 N번째 큰 수 문제는 최대 2,250,000개의 숫자를 힙이 저장해야 하는데 너무 길어서 메모리 초과가 난 것이 아닐까 생각했다.

정확한 이유를 알기 위해서 자료구조와 메모리구조를 다시 공부해야겠다.

 

따라서 이 문제는 모든 숫자를 힙에 넣는게 아니라 어차피 N번째 큰 수를 찾는 것이기 때문에 힙의 크기가 N을 유지해서 그 중 가장 작은 값을 찾으면 된다.

• 가장 첫째 줄 배열은 힙에 삽입한다.
• 힙의 크기를 일정하게 유지하기 위해 새로운 숫자가 추가될 때 마다 힙에서 가장 작은 값과 비교하고, 새로 추가되는 값이 크다면 힙에서 가장 작은 값을 삭제한 후 새로운 값을 추가한다.
  heapq.heappop(table)
  heapq.heappush(table, new)
• 마지막으로 힙에는 N개의 수가 남게 되므로 가장 작은 수를 반환하면 답을 얻을 수 있다.

import sys
import heapq

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

for _ in range(N):
    tmp = list(map(int, sys.stdin.readline().strip().split(' ')))
    if not table:
        for i in tmp:
            heapq.heappush(table, i)
    else:
        for i in tmp:
            if table[0] < i:    # 힙의 최솟값보다 클 경우,
                heapq.heappop(table)
                heapq.heappush(table, i)
                

print(table[0])

 

⚙️ Review

힙 문제를 처음 풀어봤는데 어쩐지 풀이 방법이 너무 쉽다 했더니 푸는게 다가 아닌 문제였다.

메모리는 생각도 못했는데 메모리 초과가 나와서 당황했다. 파이썬에서 힙을 사용할 수 있는 방법을 복습할 수 있는 문제였다.

시간초과 말고 메모리초과도 생각하면서 풀자