99클럽 코테 스터디_4기 19일차 TIL

TODAY TIL

안녕하세요! 여러분이 코딩 테스트에서 마주할 수 있는 흥미로운 문제를 소개합니다. 이 문제는 주어진 N×N  크기의 표에서 N번째로 큰 수를 찾아내는 것입니다. 표의 숫자들은 각자의 위에 있는 숫자보다 크도록 구성되어 있습니다. 예를 들어, N=5N = 5N=5일 때 다음과 같은 표가 있을 수 있습니다

 

12  7   9  15  5
13  8  11  19  6
21 10  26  31 16
48 14  28  35 25
52 20  32  41 49

 

이 표에서 다섯 번째로 큰 수를 찾아야 합니다.

입력 설명

• 첫 번째 줄에는 정수 NNN이 주어집니다 (1≤N≤1,5001 \leq N \leq 1,5001≤N≤1,500).
• 그 다음 NNN개의 줄에는 각 줄마다 NNN개의 정수가 주어집니다.
• 숫자들은 −109-10^9−109 이상 10910^9109 이하의 범위를 가지며, 모두 다릅니다.

출력 설명

• 프로그램은 NNN번째로 큰 수를 출력해야 합니다.

해결 전략

이 문제는 단순히 표를 정렬하여 NNN번째로 큰 수를 찾는 방식으로는 효율적이지 않습니다. NNN의 최대값이 1,500이므로 표에 있는 요소의 수는 최대 2,250,000개가 됩니다. 이 큰 데이터를 다룰 때 메모리와 시간 복잡도를 고려해야 합니다.

최적의 해결책은 다음과 같습니다:

1. 최소 힙(min-heap)을 사용하여 NNN개의 가장 큰 수를 유지합니다.
2. 한 줄씩 입력을 받아 즉시 처리하여 메모리 사용을 줄입니다.

코드 설명

이제 문제를 해결하는 코드를 단계별로 설명하겠습니다.

 

import sys
import heapq

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

# N을 입력받음
N = int(input.readline().strip())
min_heap = []  # 최소 힙을 저장할 리스트

# N개의 행에 대해 각 숫자를 읽어들임
for _ in range(N):
    row = map(int, input.readline().split())  # 한 줄의 숫자를 공백 기준으로 분리하여 처리
    for num in row:
        # 힙의 크기가 N보다 작은 경우 숫자를 추가
        if len(min_heap) < N:
            heapq.heappush(min_heap, num)
        else:
            # N개의 숫자가 이미 힙에 있으면, 새로운 숫자가 최소값보다 큰 경우 교체
            if num > min_heap[0]:
                heapq.heappushpop(min_heap, num)

# 힙의 최솟값이 N번째로 큰 수가 됨
print(min_heap[0])

 

코드 설명 (더 자세히)

• heapq 모듈은 Python에서 힙 자료구조를 다룰 수 있는 모듈입니다. 이 문제에서는 최소 힙을 사용해 NNN개의 가장 큰 수를 유지합니다.
• sys.stdin.readline(): 표의 크기가 크기 때문에, 입력을 빠르게 받기 위해 input() 대신 sys.stdin.readline()을 사용했습니다. 이는 큰 입력을 더 효율적으로 처리합니다.
• 히프 유지: 힙에 NNN개의 요소만 유지하여 메모리를 절약합니다. 새로운 숫자가 힙의 최솟값보다 클 경우에만 추가하고 기존 최소값을 제거합니다.

예제 실행

입력 예시

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

 

이 경우, 다섯 번째로 큰 수는 35입니다. 프로그램은 이 값을 올바르게 출력합니다.

시간 및 공간 복잡도 분석

• 시간 복잡도: O(N2log⁡N)O(N^2 \log N)O(N2logN). 각 숫자마다 힙 연산이 O(log⁡N)O(\log N)O(logN)이고 총 N2N^2N2개의 숫자를 처리합니다.
• 공간 복잡도: O(N)O(N)O(N). 힙의 크기는 항상 NNN으로 유지되므로 메모리 사용량이 제한적입니다.

결론

이 접근법은 메모리와 시간 효율성을 모두 고려하여 NNN번째로 큰 수를 찾는 데 적합합니다. 만약 여러분이 비슷한 문제나 더 좋은 최적화 방법을 알고 있다면 댓글로 알려주세요!

이제 이 코드와 설명을 통해 여러분도 이 문제를 해결할 수 있기를 바랍니다. 코딩 테스트나 실무 프로젝트에서도 도움이 되길 바랍니다!