1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
""" #! 이렇게 하면 시간 초과
import sys
# 명령의 수 N을 선언한다.
N = int(sys.stdin.readline())
A = [0] * N
for i in range(N):
A[i] = int(sys.stdin.readline())
for i in range(N-1):
flag = False
for j in range(N-1-i):
if A[j] > A[j+1]:
flag = True
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
if flag == False:
print("answer: ", A[i])
break
"""
"""
이 경우, A는 [(10,0), (1,1), (5,2), (2,3), (3,4)]이고, sorted_A는 [(1,1), (2,3), (3,4), (5,2), (10,0)]가 됩니다.
각 원소의 이동 거리를 계산하면 다음과 같습니다:
• 원소 1은 인덱스 1에서 인덱스 0으로 이동했으므로, 이동 거리는 1 - 0 = 1
• 원소 2는 인덱스 3에서 인덱스 1으로 이동했으므로, 이동 거리는 3 - 1 = 2
• 원소 3는 인덱스 4에서 인덱스 2로 이동했으므로, 이동 거리는 4 - 2 = 2
• 원소 5는 인덱스 2에서 인덱스 3으로 이동했으므로, 이동 거리는 2 - 3 = -1
• 원소 10은 인덱스 0에서 인덱스 4로 이동했으므로, 이동 거리는 0 - 4 = -4
여기서 가장 큰 이동 거리는 2입니다. 따라서 최적화된 버블 소트의 최종 결과는 최대 이동 거리인 2에 1을 더한 3입니다.
"""
import sys
N = int(sys.stdin.readline())
A = []
for i in range(N):
A.append((int(sys.stdin.readline()),i))
Max = 0
sorted_A = sorted(A)
for i in range(N):
if Max < sorted_A[i][1] - i: # sorted_A[i][1]은 정렬된 배열에서 원소가 원래 배열의 어느 위치에서 왔는지를 나타냄
Max = sorted_A[i][1] - i # i는 정렬된 배열에서의 현재 인덱스
print(Max + 1)
|
