[백준/Python] 2075_N번째 큰 수_Python 풀이

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

2075번: N번째 큰 수

N번째 큰 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	12 MB	14136	5716	4011	39.498%

문제

---

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

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

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

---

첫째 줄에 N번째 큰 수를 출력한다.

예제 입력 1

---

5
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

예제출력1

---

35

풀이

---

1. 첫째 줄에 주어진 횟수만큼 N개 줄을 반복하도록 하였다.

 

2. 줄 전체를 받아와서, 그 요소 하나하나마다 (-요소, 요소) 의 튜플 형태로 묶어서 q란 리스트에 넣었다.

(heapq는 최소 힙으로 만들어진다. 따라 (-요소, 요소) 형태의 튜플로 만들어서 넣게되면 튜플의 0번 위치값을 기준으로 나열되기에 최대 힙으로 생성된다.)

 

e.g) 1, 2, 3 의 최댓값 순서 (3, 2, 1) , 이는 절대 값일 경우, 역순의 최솟값 순서 (-3, -2 , -1 ) 같다.

 

3. 이후 모든 수를 원하는 것이 아니라 N번째 큰 수 까지만 필요하므로, 힙을 길이가 N인 최대 힙으로 다시 정리하였다.

 

4. 모든 케이스가 다 들어가면 최종적으로 결정된 N번째 큰 수가 출력되도록 하였다.

 

위의 예시의 경우의 과정을 모두 출력하면 이는 다음과 같다.

※ 아래의 케이스 모두 Python3로 제출할 경우, 정상적으로 통과하지만 pypy3로 제출할 경우 모두 메모리 초과가 발생한다.

 

import heapq                             #heapq 모듈을 사용하기 위해 불러오기

N = int(input())                           #숫자 N 받아오기

q = []                                       #heap을 저장하기 위한 리스트 

for _ in range(N):                         # N번 동안 반복

    for n in map(int, input().split()):   #받아올 각각의 수

        heapq.heappush(q, (-n, n))    #(-원소,원소)의 힙 형태로 입력

    q = heapq.nsmallest(N, q)         #(-원소, 원소)의 힙을 길이가 N이 되도록 가장 작은 수(최대 힙 순서)로 재정렬

print(q[N-1][1])                           #N번째 큰 수 출력

---

 

#sys를 사용한 경우

 

import sys

import heapq

N = int(sys.stdin.readline())

q = []

for _ in range(N):

    for n in map(int, sys.stdin.readline().split()):

        heapq.heappush(q, (-n, n))

    q = heapq.nsmallest(N, q)

print(q[N-1][1])

---