URL : https://www.acmicpc.net/problem/2075
문제
- 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번째 큰 수를 출력한다.
문제 풀이
- 해당 문제는 메모리 제한이 있는 문제임
- 우선 처음 주어지는 입력 만큼 for문을 돌림
- 이후 주어지는 N개의 숫자를 입력 받음
- python의 bisect를 사용하면 자동으로 sort된 상태로 입력이 됨
- 처음 N개의 배열이 될때까지는 우선 a배열에 입력
- 배열의 N번쨰 큰 수를 k로 지정
- 이후 k 보다 작은 숫자가 들어오면 배열에 입력하지 않음 (메모리 절약)
- N보다 큰 숫자만 넣고, 매번 k를 갱신함.
- 마지막에 N번째 큰수를 출력하기 위해 배열에 -를 붙임
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import bisect
import sys
# N = int(input())
N = int(sys.stdin.readline().strip())
a = []
for _ in range(N):
# j = input()
j = sys.stdin.readline().strip()
for i in j.split():
if len(a) <= N:
bisect.insort_left(a, int(i))
else:
k = a[-N]
if int(i) < k:
pass
else:
bisect.insort_left(a, int(i))
print(a[-N])
1
2
3
4
5
6
7
8
9
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
35