[Boj/백준] 2075 Python

문제출처: https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

 

1. 문제 접근 방식

배열을 있는 그대로 다 append하면 시간초과 혹은 메모리초과가 발생할 것 같았다.

그래서 최대한 덜 append하는 방법을 생각하다가

첫 행의 원소는 힙에 다 삽일을 하고

두번째 행의 원소부터는 하나씩 꺼내서 heappop한거보다 크면 heappush하고 아니면 원래 heappop한 원소를 다시 heappush하는 방식으로 풀었다.

 

 

2. 내가 푼 코드

import sys
import heapq
n = int(sys.stdin.readline())

graph = []
heap = []
heapq.heapify(heap)

first_arr = list(map(int,sys.stdin.readline().split()))
for i in first_arr:
    heapq.heappush(heap,i)

for _ in range(n-1):
    arr = list(map(int,(sys.stdin.readline().split())))
    heapq.heapify(arr)
    for i in arr:
        a = heapq.heappop(heap)
        if i > a:
            heapq.heappush(heap,i)
        elif i < a:
            heapq.heappush(heap,a)

print(heapq.heappop(heap))

 

 

3. 결과 및 느낀점

메모리가 부족할거 같을때는 원소를 무작정 다 배열에 넣지 말고

하나하나 끊어서 넣고 비교하자 정렬 문제에는,,,

특히 2차원 리스트에서는

행마다 끊어서!