[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번째 큰수를 구하는 거였고, N의 최대값이 1500이므로, 전체 input을 받아서 행렬을 만드는게 아닌, 

 

한 행이 들어올때마다 판별을 해줘야한다고, 생각했다.

 

그리고 우리가 구하고 싶은 것은 N번째 이므로, 저장할 칸은 N 칸만 있으면 된다고 생각했고, 이걸 heapq를 이용해서 구현했다.

 

처음 구현한 방식은 일단 한 행을 전부 집어넣고, 리스트의 길이가 N이 될때까지 heappop을 계속 해주었다. 

 

그리고 마지막으로 heappop을 해서 원하는 결과를 얻었다.

 

 

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 모듈을 좀 더 활용하는 방법이다.  무조건 넣고 길이 N이 될때까지 계속 pop 하는 것이 아닌.

 

heappushpop을 쓰는 것이다. 이것은 heap에 먼저 push를 한뒤에 가장 작은 값을 pop 하는 것으로,

 

heappush와 heappop을 쓰는 것보다 실행속도가 더 빠르다.

 

그리고 마지막으로 heapq.nlargest를 쓰는 것이다. 이 메소드는 정의된 요소에서 가장 큰 순서대로 n개로 구성된 리스트를 반환해주는 메소드이다. 이걸 이용하면, 정렬을 한 효과와 동일하다.

 

# 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

마지막 풀이는 stkang9409님 코드를 보고 분석하것이다.

이 방법은 heapq를 쓴 것이 아닌, 문제의 조건을 보고 푼 방식이다.

 

위의 heapq를 쓴다면 신경 안 쓸 조건이지만, 문제에 주어진 조건을 보면

 

각 열의 값들은 그 다음행의 값보다 작다는 것이다. 즉 A열의 B행의 값은 B+1행보다는 무조건 작다는 것이다.

 

이 점을 이용해 N번째로 큰 값을 알 수 있다.

 

 

만약 조건 N이 주어진다면

 

각 열마다 가장 큰 행의 위치는 N-1일것이다. (0행부터 시작한다)

 

이걸 하나의 리스트로 구성하면

max_row_list = [N-1, N-1,.... N-1]

일것이고, 이 리스트의 인덱스는 arr의 열의 값이 될것이고, 해당 index의 값은 행이 될것이다.

 

각 열에서의 최대값을 비교해서 가장 큰 값을 구해준다.

 

각 열의 최대값은 arr[ max_row_list[ind] ] [ ind ] 가 될 것이다.

 

이렇게 하면 가장 큰 값이 있는 열의 값을 구할 수 있다. 그 열의 값이 있는 max_row_list의 값을 1을 낮춰준다.

 

이런 식으로 반복 하면 N번 반복하면 N번째로 큰 수를 알 수 있다.

 

 

예시 ) 

12 7 9 15 5

13 8 11 19 6

21 10 26 31 16

48 14 28 35 25

52 20 32 41 49

 

위와 같이 주어지면 

 

max_row_index = [4,4,4,4,4] 가 될 것이다.

 

--  1번째  --

 

arr[4][0],arr[4][1],arr[4][2],arr[4][3],arr[4][4] 의 값을 비교해보면 arr[0][4]가 가장 작다.

 

그러면 max_row_index 의  0번 인덱스의 값을 1 줄여준다,

 

max_row_index = [3,4,4,4,4] 가 된다.

 

-- 2번째 --

 

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[4][4] 의 값을 비교해보면 arr[4][4]의 49가 가장 크다.

 

그러면 4번 인덱스이고 해당 max_row_index의 값을 줄여준다.

 

max_row_index = [3,4,4,4,3]

 

-- 3번째 --

 

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교해보면 arr[3][0]의 48이 가장 크다.

 

그러면 0번 인덱스이고 해당 max_row_index의 값을 줄여준다.

 

max_row_index = [2,4,4,4,3]

 

 

-- 4번째 --

 

arr[2][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교 해보면  arr[4][3]의 41이 가장 크다.

 

그러면 3번 인덱스이고 해당 max_row_index의 값을 줄여준다.

 

max_row_index = [2,4,4,3,3] 

 

--5번째 (마지막) --

 

arr[2][0],arr[4][1],arr[4][2],arr[3][3],arr[3][4] 의 값을 비교 해보면 arr[3][3]의 35이 가장 크다

 

그리고 우리가 구하던 N번째로 큰 값이므로 이 값을 그대로 출력해주면 된다.

 

 

설명이 많이 부족하겠지만, 최대한 자세히 설명을 했다.

 

 

마지막 풀이는 문제의 조건을 활용해 각 열을 기준으로 하는 최대 행을 저장해주는 리스트를 만들어두고

 

각 열의 최대값을 갱신해주면서 하는 방식으로 보면 된다.