[Python] 백준 2075 N번째 큰 수

 

문제 분석

• n x n
• 모든 수는 자신의 한 칸 위에 있는 수보다 크다.
• n번째로 큰 수를 찾아라

 

코드 설계

1차

• 싹다 모아서 일렬로 정렬한 뒤 n번째의 수 출력? - 시간초과 날거같은데..

2차

• 우선순위 큐

 

정답 코드

1차 - 실패 (메모리 초과)

import sys
input = sys.stdin.readline

n = int(input())
g = []
for _ in range(n):
    g.append(list(map(int,input().split())))

ans = []
for i in range(n) :
    for j in range(n):
        ans.append(g[i][j])

ans.sort(reverse=True)
print(ans[n-1])

 

2차 실패...

import sys
input = sys.stdin.readline

import heapq

n = int(input())
g = []
for _ in range(n):
    g.append(list(map(int,input().split())))

h = []
for i in range(n):
    for j in range(n) :
        heapq.heappush(h, g[i][j])

print(h[n*n-n])

 

다른 사람 코드 1

https://naroforme.tistory.com/entry/%EB%B0%B1%EC%A4%80-2075%EB%B2%88-N%EB%B2%88%EC%A7%B8-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

파이썬 heapq 모듈을 통해 힙을 만들면
최소힙(min heap)이 만들어지고
최소힙 구조에서 조건문을 사용하여
힙 원소의 push, pop을 제어해 최소한의 메모리 사용을 하는것이 목표

import sys
input = sys.stdin.readline

import heapq as hq

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

init_num = list(map(int, input().split()))
for num in init_num :
    hq.heappush(heap, num)

for i in range(n-1):
    numbers = list(map(int, input().split()))
    for num in numbers :
        if heap[0] < num :
            hq.heappush(heap, num)
            hq.heappop(heap)
print(heap[0])

 

 

2회차 - 25.02.13

1. heapq를 어떻게 활용해야 할까?
2. heappush를 하면 최소값이 출력된다.
3. 최대 힙으로 바꿔서 n번째 pop되는게 n번째 큰 수 아닐까?

 

1차 - 메모리 초과

import sys
input = sys.stdin.readline
import heapq

n = int(input())

h = []
for i in range(n) :
    nums = list(map(int, input().split()))
    for num in nums :
        heapq.heappush(h, -num)

ans = []
for _ in range(n) :
    v = heapq.heappop(h)
    ans.append(v)

print(-ans[-1])

 

2차

import sys
input = sys.stdin.readline
import heapq

n = int(input())
h = []
for i in range(n) :
    num_list = list(map(int, input().split()))
    if not h : # h에 값이 없으면
        for num in num_list :
            heapq.heappush(h, num)
    else : # 값이 있으면 항상 h의 길이를 n으로 유지
        for num in num_list :
            if h[0] < num : # 현재 힙의 최솟값보다 현재 숫자가 더 클 경우, 큰 수가 바뀌어야 한다.
                heapq.heappush(h, num)
                heapq.heappop(h)
                
print(h[0]) # 5번째 큰 수부터 가장 큰 수까지 힙에 담겨잇음