4/19 스터디 문제

1번 문제.
https://www.acmicpc.net/problem/2075
-> N번째 큰 수

1-1번 문제 풀이 코드 (메모리 초과)

import sys
from collections import deque

n = int(sys.stdin.readline())
nums = deque()

for _ in range(n):
    nums.append(deque(map(int, sys.stdin.readline().rstrip().split())))

list = []
for i in range(n):
    for j in range(n):
        list.append(nums[i][j])
list.sort(reverse=True)

print(list[n-1])

=======================================================
메모리 초과!!!
다른 블로그들을 찾아보니, 힙큐를 사용해서 푸는 것을 추천한다.
우선순위 큐과 힙

1-2번 문제 풀이 코드(정답)

import sys
import heapq

# nxn 보드 입력
n = int(sys.stdin.readline())
# 힙 숫자들의 리스트
num_list = []
for _ in range(n):
    # n번 숫자들을 입력 받음
    numbers = list(map(int, sys.stdin.readline().rstrip().split()))

    # 저장할 리스트에 값이 없으면
    if not num_list:
        # 입력 받은 숫자들을 하나씩
        for num in numbers:
            # num_list에 숫자(num)를 넣는다.
            # heappush를 이용해서 리스트에 최솟값부터 담긴다.
            heapq.heappush(num_list, num)
            # print(num_list)

    else:
        for num in numbers:
            # 만약 리스트 내에서 최솟값이 입력 받은 수보다 작으면
            if num_list[0] < num:
                # 입력 받은 수를 num_list에 넣어준다.
                heapq.heappush(num_list, num)
                # print(num_list)
                # 그리고 최솟값(num_list[0])을 하나씩 제거
                heapq.heappop(num_list)
                # print(num_list)
# print(num_list) -> 최솟값들을 하나씩 제거하고나면, num_list에는 가장 큰 수 n개가 순서대로 남아 있다.
print(num_list[0])

[12][7, 12]
[7, 12, 9][7, 12, 9, 15]
[5, 7, 9, 15, 12]
그 다음에 13이 온다.
[5, 7, 9, 15, 12, 13][7, 12, 9, 15, 13] 최솟값 5 제거 후 그 다음 최솟값이 앞에 채워짐
[7, 12, 8, 15, 13, 9][8, 12, 9, 15, 13]
[8, 12, 9, 15, 13, 11][9, 12, 11, 15, 13]
[9, 12, 11, 15, 13, 19][11, 12, 19, 15, 13]
[11, 12, 19, 15, 13, 21][12, 13, 19, 15, 21]
[12, 13, 19, 15, 21, 26][13, 15, 19, 26, 21]
[13, 15, 19, 26, 21, 31][15, 21, 19, 26, 31]
[15, 21, 16, 26, 31, 19][16, 21, 19, 26, 31]
[16, 21, 19, 26, 31, 48][19, 21, 48, 26, 31]
[19, 21, 28, 26, 31, 48][21, 26, 28, 48, 31]
[21, 26, 28, 48, 31, 35][26, 31, 28, 48, 35]
[26, 31, 28, 48, 35, 52][28, 31, 52, 48, 35]
[28, 31, 32, 48, 35, 52][31, 35, 32, 48, 52]
[31, 35, 32, 48, 52, 41][32, 35, 41, 48, 52]
[32, 35, 41, 48, 52, 49][35, 48, 41, 49, 52]

=======================================================
힙큐 문제들을 몇 번 더 풀어봐야 할 듯 하다.