https://codeforces.com/contest/1525/problem/B
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 2000)
- n (3 ≤ n ≤ 50)
- n distinct integers from 1 to n
output :
- For each test case, output a single integer — the minimum number of operations described above to sort the array a in ascending order.
배열을 오름차순으로 정렬하기 위한 최소한의 수행 횟수를 출력하시오.
조건 :
- You can perform the following operation: choose some subarray (contiguous subsegment) of a and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array.
부분 배열을 설정한 후에 이를 정렬 한다. 이 부분 배열은 전체가 될 수 없다. 이와 같은 행동을 수행한다.
배열을 정렬할 때 우리가 선택할 수 있는 가장 큰 배열이 무엇일까?
1개를 제외한 나머지를 정하는 것이다.
그렇다면 우리는 인제 조건을 설정할 수 있다.(숫자들은 인덱스를 나타낸다.)
0에 가장 작은 숫자. -1에 가장 큰 숫자.
조건
우리가 가진 수들은 1 ~ n 까지이다. 그 말은 가장 작은 숫자는 1이고 가장 큰 거는 n으로 고정된다는 의미이다.
반복문을 돌면서 값을 비교할 필요가 없다.
경우
위치 0 : n and 위치 -1 : 1 인 경우
3번의 교체가 필요하다. [0, n - 1]까지 정렬, [n - 1, n] 정렬, [0, n - 1] 정렬을 통해 만들어 준다.
위치 0 : 1 or 위치 -1 : n인 경우
1번의 교체가 필요하다. 자신을 제외한 나머지를 정렬한다.
그 외의 경우에는 2번의 교환이 필요하다.(큰것을 정렬한 후에 작은 것을 완성하던지. 수의 크기가 작은 놈 먼저 이후에 큰 놈 정렬)
이미 정렬이 된 것은 0을 출력하자.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
min_val, max_val = data[0], data[0]
diff = 0
for idx in range(1, len(data)):
if data[idx] < data[idx - 1]:
diff = 1
if diff == 1:
if data[0] == 1 or data[-1] == n:
print(1)
elif data[-1] == 1 and data[0] == n:
print(3)
else:
print(2)
else:
print(0)
