HackerRank New Year Chaos

리스트 원소가 오름차순 정렬되도록 해야 하는데 조건이 있다.
1. 각 원소는 뒤에 원소랑 자리 교환을 할 수 있다.
2. 각 원소는 자리 교환을 2번만 할 수 있다
자리 교환 최소 횟수를 출력한다. 만약 원소가 자리 교환을 2번 초과한다면 Too chaotic을 출력한다

일일이 정렬하지 않아도 Too chaotic인 경우를 index와 원소 값을 통해 알 수 있다. 이때 바로 Too chaotic을 출력하고 종료한다
버블 정렬을 활용해야 한다
정렬 flag를 하나 두고 False로 유지된다면 정렬된 상태이므로 횟수를 출력하고 종료한다

시간 초과가 자꾸 났는데 정렬이 필요 없는 상황에선 종료해주면 된다
Big O가 n^2이기 때문에 10만^10만이면 상당히 느리다.

#!/bin/python3


def minimumBribes(q):
    length = len(q)
    swapped = False
    for i, v in enumerate(q):
        if v - 1 > i + 2:
            print("Too chaotic")
            return

    count = 0
    for i in range(length - 1):
        for j in range(length - 1):
            if q[j] > q[j + 1]:
                count += 1
                q[j], q[j + 1] = q[j + 1], q[j]
                swapped = True

        if swapped:
            swapped = False
        else:
            print(count)
            return


if __name__ == '__main__':
    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        q = list(map(int, input().rstrip().split()))

        minimumBribes(q)