문제:

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

12 

15 

13 

11 

19 

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번째 큰 수를 출력한다.

풀이 방법:

 처음에는 모든 값을 다 담아서 n번 빼는 방식으로 했더니 메모리초과가 발생했다. N이 최대 1500까지 가능하니 1500^2개가 있으니 그럴만하다. 이 문제에서 원하는 것은 상위 N개를 원하는 것이다. 따라서 상위 N개만 담는 최소 힙을 만들고 모든 표를 다 본 뒤에 가장 작은 값을 찾으면 N번째 큰 수를 얻을 수 있다고 생각했다. heapq를 자세히 알아보니 heappop()으로 가장 작은 값을 빼낼 수 있지만 빼지 않고 arr[0]과 같이 접근 하면 가장 작은 값을 얻을 수 있다고 한다. 따라서 이를 이용해 answer에 가장 작은 값보다 큰 값이 들어오면 작은 값을 빼내고 큰 값을 넣는 방식으로 상위 N개 배열을 유지하였다.
 이 문제는 애초에 pypy3으로 제출해서 python3에서 어떻게 동작할지는 잘 모르겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
answer=[]
heapq.heapify(answer)
n=int(input())
for i in range(n):
    numbers=list(map(int,input().split()))
    if i==0:
        for number in numbers:
            heapq.heappush(answer,number)
        minItem=answer[0]
    else:
        for number in numbers:
            if number > minItem:
                heapq.heappush(answer,number)
                heapq.heappop(answer)
                minItem=answer[0]
print(answer[0])
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]10816. 숫자 카드2  (0) 2019.07.25
[BOJ]1920. 수 찾기  (0) 2019.07.24
[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙  (0) 2019.07.21
[BOJ]2606. 바이러스  (0) 2019.07.20
[BOJ]1260. DFS와 BFS  (0) 2019.07.19

+ Recent posts