[BOJ] 2075 N번쨰 큰 수

date

Aug 14, 2023

slug

boj-2075

author

status

Public

문제 링크

https://www.acmicpc.net/problem/2075

문제

N×N의 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=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

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

문제풀이

메모리 제한이 12MB이기 때문에

입력 크기 ≤ 1500 * 1500을 배열에 저장할 수 없고 정렬도

225만logn이 시간 초과가 날 수 있는 상황이라, 특별한 자료구조를 고안하였다

먼저 최소힙을 선언해주고, 입력으로 들어온값을 오름차순으로 정렬한 후에

최소힙의 크기가 N보다 클경우에, 최소값을 빼주고 값을 넣어준다.

이때 최소힙에 있는 최소값은 항상 입력값보다 작음을 만족한다.

그러므로 최소힙의 0번째 인덱스는 항상 배열에서 N번째 큰 수 이고

최소힙에서 값을 빼면 N-1, N-2.. .. 가장 큰 수를 얻어낼 수 있다.

직접 그림을 그렸을때

5x5를 정렬한 결과이고, 오른쪽은 우선순위 큐에 삽입, 제거하는 과정을 계속 그린 것이다.

과정을 보면 진행과정에서 계속 0번째인덱스는 N번째 큰 수임을 만족하는 것을 볼 수 있다.

파이썬 문제풀이 코드


import heapq
import sys
input = sys.stdin.readline

N = int(input())

min_pq = []
for i in range(N):
    for j in sorted(map(int, input().split())):
        if len(min_pq) <= N-1:
            heapq.heappush(min_pq, j)
        else:
            heapq.heappop(min_pq)
            heapq.heappush(min_pq, j)
    # print(min_pq)
print(min_pq[0])

# print(min_pq)

시간복잡도

O(n* nlogn)

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

예제 입력


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

예제 출력

알고리즘 분류

자료 구조

정렬

우선순위 큐