728x90
반응형
문제:
N X N 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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번째 큰 수를 출력한다.
풀이 방법:
처음에는 모든 값을 다 담아서 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 |
728x90
반응형
'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 |