버블정렬과 swap

문제 설명

길이가 최대 10,000인 정수 일차원 배열 numbers가 주어집니다. 이 배열을 아래와 같은 버블 정렬로 오름차순 정렬할 때, 인접한 두 값이 교환(swap)되는 연산이 총 몇 번 발생하는지 계산해 반환하는 solution 함수를 작성하시오.

버블 정렬의 pseudo code

FUNCTION bubbleSort(numbers)
    n ← length of numbers

    FOR i FROM 0 TO (n - 2) DO
        FOR j FROM 0 TO (n - 2 - i) DO
            IF numbers[j] > numbers[j + 1] THEN
                SWAP numbers[j] WITH numbers[j + 1]
            END IF
        END FOR
    END FOR

    RETURN numbers
END FUNCTION

예를 들어, numbers = [5,1,4,2,8] 인 경우 swap 횟수는 아래와 같습니다.

[(5,1),4,2,8] → [(1,5),4,2,8] (5와 1 swap, 누적 1회)
[1,(5,4),2,8] → [1,(4,5),2,8] (5와 4 swap, 누적 2회)
[1,4,(5,2),8] → [1,4,(2,5),8] (5와 2 swap, 누적 3회)
[1,(4,2),5,8] → [1,(2,4),5,8] (4와 2 swap, 누적 4회)

제한 사항

• numbers의 길이 n은 1 이상 10,000 이하입니다.

• numbers의 각 원소는 -100,000 이상 100,000 이하의 정수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 문제에서 제시한 예시와 동일하며 swap이 이루어지는 경우는 다음과 같습니다.

[(5,1),4,2,8] → [(1,5),4,2,8] (5와 1 swap, 누적 1회)
[1,(5,4),2,8] → [1,(4,5),2,8] (5와 4 swap, 누적 2회)
[1,4,(5,2),8] → [1,4,(2,5),8] (5와 2 swap, 누적 3회)
[1,(4,2),5,8] → [1,(2,4),5,8] (4와 2 swap, 누적 4회)

2번 테스트케이스 설명

• swap이 이루어지는 경우는 다음과 같으며 총 3번의 swap이 발생합니다.

[(3,2),1] → [(2,3),1] (3과 2 swap, 누적 1회)
[2,(3,1)] → [2,(1,3)] (3과 1 swap, 누적 2회)
[(2,1),3] → [(1,2),3] (2와 1 swap, 누적 3회)

3번 테스트케이스 설명

• 이미 오름차순 정렬된 [1,2,2,3,3]는 swap이 한 번도 발생하지 않으므로 0을 반환합니다.