A. Simply Strange Sort | Round #740 Div.2

https://codeforces.com/contest/1561/problem/A
시간 2초, 메모리 512MB

input :

• t (1 ≤ t ≤ 100)
• n (3 ≤ n ≤ 999)
• a1, a2, ..., an(1 <= ai <= n)

output :

• For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.

If the given permutation is already sorted, print 0.
각 테스트케이스에서 몇 번의 반복이 발생하는 지 출력하시오. 이미 정렬되어 있는 순열의 경우에는 0을 출력하시오.

조건 :

• You have a permutation: an array a = [a1, a2, ..., an] of distinct integers from 1 to n. The length of the permutation n is odd.
  배열 a를 입력받습니다. 이 순열은 1 ~ n으로 구성되어 있고 길이는 홀수입니다.

• If ai > ai + 1, the values of ai and ai + 1 are exchanged.
  이 배열을 정렬하기 위해 f(i) 알고리즘을 사용하는데 ai 와 ai + 1을 비교하여 뒤의 원소가 더 클 경우에 두 원소의 위치를 바꿔줍니다.

• if i is odd, call f(1),f(3),…,f(n−2);
  if i is even, call f(2),f(4),…,f(n−1).
  만약 i가 홀수라면 홀수들에 대해 위의 알고리즘을 적용하고 짝수인 경우에는 짝수들에게만 적용합니다.

수의 위치가 변경되는 횟수를 찾는 것이 아니라.
오름차순으로 정렬을 완료하기 까지 반복이 몇 번 발생하는지를 찾는 것이다.

그렇게 따지면 길이가 999짜리 배열이기 때문에 모든 홀, 짝의 위치가 바뀐 배열이라 생각할 때.
최대한의 반복 999번에 숫자들을 교환하기 위해 한 450번 반복을 한다 해도 그다지 큰 수는 아니다.

직접 수행을 하도록 하자.

import sys

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    ans = []

    for i in range(n):
        temp = 0

        for j in range(i % 2, n, 2):
            if j + 1 < n and data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                temp += 1
        ans.append(temp)

    temp = 0
    for i in range(n - 1, -1, -1):
        if ans[i] != 0:
            temp = i + 1
            break

    print(temp)

n번 동안 수행을 하게 한 다음에 ans배열을 통해 더 이상 수의 변화가 발생하지 않는 지점을 찾도록 하였다.