99클럽 코테 스터디 20일차 TIL + 오늘의 학습 키워드 : 힙

오늘의 항해99클럽의 키워드는 어제와 같은 '힙' 이다.

문제를 보았을 때는 최대힙으로 풀어야하나하고 풀면,
메모리초과문제가 발생했다.

결국은, 또 다시 최소힙을 이용하여 문제를 풀게되는데, 먼저 문제를 보자면,
백준2075번 문제_N번째 큰 수 

 

문제풀이
: 이 문제는 N×N 크기의 표에서 N번째로 큰 수를 찾는 것이므로, 최대 힙을 구하는 것과 유사한 방식으로 접근할 수 있습니다. 하지만 실제로는 최소 힙을 사용하여 N개의 가장 큰 수를 유지하는 방식입니다. 

import heapq
import sys

# 입력을 빠르게 받기 위해 sys.stdin.readline 사용
input = sys.stdin.readline

def find_nth_largest(N):
    # 최소 힙을 초기화
    min_heap = []
    
    # N개의 행을 반복
    for _ in range(N):
        # 각 행의 수를 입력받아 리스트로 변환
        row = list(map(int, input().split()))
        # 각 수를 힙에 추가
        for num in row:
            heapq.heappush(min_heap, num)  # 수를 힙에 추가
            # 힙의 크기가 N을 초과하면 가장 작은 수를 제거
            if len(min_heap) > N:
                heapq.heappop(min_heap)  # 최소 힙에서 가장 작은 수 제거
    
    # 힙의 루트는 N번째로 큰 수
    return min_heap[0]

# 첫 번째 줄에서 N을 입력받기
N = int(input().strip())

# N번째 큰 수 찾기
result = find_nth_largest(N)
print(result)  # 결과 출력

주석 설명
1. 입력 처리: sys.stdin.readline을 사용하여 입력을 빠르게 처리합니다. 이는 대량의 입력을 다룰 때 유리합니다.
2. 최소 힙 초기화: min_heap 리스트를 사용하여 최소 힙을 구현합니다.
3. 행 반복: N개의 행을 반복하면서 각 행의 수를 입력받습니다.
4.힙에 수 추가: 각 수를 힙에 추가하고, 힙의 크기가 N을 초과할 경우 가장 작은 수를 제거하여 항상 N개의 가장 큰 수만 유지합니다.
5. 결과 반환: 최종적으로 힙의 루트에 있는 수가 N번째로 큰 수이므로 이를 반환합니다.
이 방식은 메모리 사용을 최적화하면서도 효율적으로 N번째로 큰 수를 찾을 수 있는 방법입니다.