[백준-Python] N번째 큰 수 : 2075번

🥈 Silver2

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

 

 

❎ 1차 풀이

import sys

# maxHeap
# 줄마다 가장 큰 값 비교후 가장 큰 값은 pop

input = sys.stdin.readline
n=int(input())

heap=[]

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

#세로줄로 heap 생성
heap_list=[]
for i in range(n): #row
    t=[]
    for j in range(n): #col
        t.append(temp[j][i])
    heap_list.append(t)
print(heap_list)

# 리스트 순회하면서 가장 큰 수 뽑기
for i in range(n):
    num=heap_list[i][len(heap_list[i])-1]
    if num==max()

처음엔, 한줄마다 maxHeap으로 구현되어있다는 생각에 크게 볼생각을 못했다....

그런데 세로로 읽어야하기 때문에 이중 for문으로 리스트를 만들고, 그 리스트들을 maxHeap으로 관리해서 가장 큰 값을 pop으로 빼내면서 n번째 값을 리턴하면 되지 않을까 이런생각을 했다... 

근데 이걸 코드로 옮기면서 2중 for문부터 이게 맞나 싶기도 했고,

가장 큰 문제는 heap은 가장 첫번째 값을 기준으로 힙정렬이 이루어지는데 그렇다고 [12, 13, 21, 48, 52] 이 줄을 reverse해버리면 pop이 아닌 shift가 되면 너무 비효율적이다... 

그래서 이방법은 더이상은 안되겠다 싶어서 접었다 🙄

 

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

 

❎ 2차 풀이

input = sys.stdin.readline
n=int(input())

heap=[]

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


for i in range(n-1):
    heapq.heappop(heap)

print(heap[0][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

[백준] 2075번 : N번째 수 파이썬

 

이 포스팅을 참고해서, 다시 작성해보았다. 

그냥 단순하게 input으로 들어오는 모든 수를 maxHeap에 담아 pop을 하면서 가장 큰값을 뽑아내는 방식이다.

실버2인데.. 역시 이방법은 메모리초과가 발생하는 문제가 있었다.

 

 

 

❗️Heap의 크기가 일정하지 않으면 메모리 초과가 발생하는 이유

 

 

검색을 해보다가, 힙을 일정한 크기로 유지해야한다길래 GPT 선생에게 바로 물어보았더니

내가 바로 저 nxn행렬의 모든 요소를 저장하였기 때문에, 메모리가 부족했나보다...

 

👉🏻 힙의크기를 n으로 유지시켜, 메모리 사용량을 제한시키자!

 

 

✅ 정답

import heapq
import sys
input = sys.stdin.readline

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

for _ in range(n):
    nums = list(map(int,input().split())) #[12,7,9,15,5]

    if not heap:
        for num in nums: 
            heapq.heappush(heap, num) # 초기값 n개 넣어주기 [5,7,9,12,15]
        
    else:
        for num in nums:
            if num > heap[0]:
                heapq.heappop(heap) # 맨앞제거하고
                heapq.heappush(heap, num) # 새로운 값 넣어주기
              
               
print(heap[0])

메모리	실행시간
33188KB	760ms

 

힙의 크기를 n의 값으로 고정해야한다는 피드백을 가지고,

n개씩 input을 받아 처음 초기값은 heappush로 설정해주고, 최종적으로 가장 큰 n개의 값만을 남겨야하기 때문에

순회를 통해 Input으로 받은 새로운 값과 힙에 존재하는 가장 작은값을 pop으로 없애준다.

그렇게 최종적으로 남은 heap은 [5,4,3,2,1]번째로 큰수들이 담겨있을것이기 때문에 0번째 인덱스값을 출력해주면된다! ✨