Posts N번째 큰 수 [Python]
Post
Cancel

N번째 큰 수 [Python]

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

문제

  • N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.
     
1279155
13811196
2110263116
4814283525
5220324149
  • 이러한 표가 주어졌을 때, 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
This post is licensed under CC BY 4.0 by the author.

메뉴 리뉴얼[Python]

명령 프롬프트 [Python]

Comments powered by Disqus.