N번째 큰 수_2075

박상민·2023년 9월 24일

백준

목록 보기

6/36

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

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

출력

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

예제

코드

sol1)

import heapq

heap = []
n = int(input())

len(heap)
for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
        else:
            if heap[0] < number: # (number가 minheap보다 클 경우) heap정렬을 유지한 채로 교체
                heapq.heappop(heap)
                heapq.heappush(heap, number)
                print(number, heap)
            #else : (number가  minheap보다 작을 경우) 아무 교체도 안일어남


print(heap[0])

sol2)

import heapq

n = int(input())

heap = []
for i in range(n):
    for j in list(map(int, input().split())):
        heapq.heappush(heap, j)  # j를 그대로 힙에 추가
        if len(heap) > n:  # 힙의 크기가 n을 초과하면 가장 작은 원소 제거
            heapq.heappop(heap)

print(heap[0])  # 힙의 가장 큰 원소가 결과

문제 접근법

원래는 문제 N^2개의 원소를 모두 입력받아 정렬 후 N의 해도 되는데 메모리 제한으로 인해 위와 같은 풀이를 제출 시 메모리 초과로 실패가 나게 됨

import heapq

n = int(input())

heap = []
for i in range(n):
    for j in list(map(int, input().split())):
        heapq.heappush(heap, -j)
        print(heap)

print((-1)* heap[n-1])

따라서 적당한 자료구조를 이용하면 되는데 우선순위 큐를 이용하면 이를 방지할 수 있다. 우선순위 큐는 일반적으로 힙을 이용해 구현하므로 힙 자료구조를 사용하였다.
정렬되어 있는 리스트의 [0]값 (가장 작은 값) 과 입력값을 비교하며 입력값을 힙에 넣으면 된다.
이때, 우선순위 큐 안에 들어있는 원소의 개수가 N개 미만이라면 우선순위 큐에 집어넣는다.
N개 이상이 될 경우 이때부터 힙정렬된 원소의 [0]값 과 새로운 원소(number)를 비교하여 새로운 원소가 클 경우 pop후 새로운 원소(number)를 넣는다. 작을 경우에는 무시한다.
이렇게 되면 N번째 큰 원소를 크기가 N인 Heap을 유지하면서 답을 찾을 수 있게 된다.

for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
            print(number, heap)
        else:
            if heap[0] < number: # (number가 minheap보다 클 경우) heap정렬을 유지한 채로 교체
                heapq.heappop(heap)
                heapq.heappush(heap, number)
                print(number, heap)
            #else : (number가  minheap보다 작을 경우) 아무 교체도 안일어남