[BOJ/백준] 2075 N번째 큰 수

import heapq
import sys
 
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)
 
 
 
result = heapq.heappop(arr)
print(result)

 

 

문제의 조건 중 N이 1500이라서 전부 arr에 저장을 하면 메모리가 부족할 가능성이 있다.

 

그래서 arr의 크기를 N으로 고정시켜놓고 그보다 클시에는 pop을 해주는 방식으로 했다.

 

import heapq
import sys
 
input = sys.stdin.readline
 
N = int(input())
arr = []
 
for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

 두번째 방식은 heapq의 기능을 좀 더 잘 쓰는것이다.

 

heappushpop을 하면 heapop을 하고 heappush를 하는 것보다 더 빠르다.

 

이걸 이용해서 위와 같이 똑같이 해주고,

마지막에는 전체 arr 중에서 N개의 큰 수 만을 뽑아내는 methods를 활용해준다.

 

# stkang9409 풀이 해석
 
def find_max_value(x):
    return arr[max_row_list[x]][x]
 
import sys
 
input = sys.stdin.readline
 
 
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
 
max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

 

다른 분의 풀이를 해석한 것으로, 문제의 조건을 활용해서 하는 방식이다.

 

각 열의 값은 다음 행의 값보다는 작다는 점을 이용해,

 

N번을 반복하면서 가장 큰 값들이 위치한 col의 row값을 하나씩 줄여주는 방식이다.