백준 1377번 버블 소트

 

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

 

풀이

 

문제에 나온 소스를 그대로 돌리면 시간초과가 나온다. 버블 정렬의 시간복잡도는 O(n^2)이기 때문이다. 따라서 버블 정렬의 규칙을 찾아내어 출력값인 정렬 수행 횟수를 구해야 한다.

 

해당 코드에서의 버블 정렬은 오름차순으로, 큰 수는 우측으로, 작은 수는 좌측으로 이동하며 정렬 된다.

이 때, 비교는 좌측(인덱스 0)부터 시작하고 우측부터 정렬이 완료 되는데, 이러한 규칙을 통해 버블 정렬이 몇 번 수행될 것인지 계산할 수 있다. 

 

문제에 나온 입력 예시를 토대로 설명하자면

 

아래와 같은 배열이 있다.

인덱스	0	1	2	3	4
값	10	1	5	2	3

 

이 배열의 각각 요소들에 대한 인덱스를 기억해두고, 어떤 정렬이어도 상관 없으니 성능이 괜찮은 정렬을 수행 한다.

 

이전 인덱스	1	3	4	2	0
현재 인덱스	0	1	2	3	4
value	1	2	3	5	10

 

위와 같이 정렬이 되었을 것이다.

이전 인덱스와 현재 인덱스만을 비교해보자.

이전 인덱스	1	3	4	2	0
현재 인덱스	0	1	2	3	4

 

 

첫 번째 항목을 보면, 1번 인덱스에 있던 값이 0번 인덱스로 이동했다는 것을 알 수 있다.

 

1번에서 0번으로 가려면, 몇 번 이동해야할까? 1번이다. 

3번에서 1번으로 가려면? 2번.

4번에서 2번으로 가려면? 2번.

 

즉, 이전 인덱스에서 현재 인덱스의 값을 빼주면 이동 횟수를 알 수 있다.

 

그러면 모두 계산을 해보자.

 

이전 인덱스	1	3	4	2	0
현재 인덱스	0	1	2	3	4
인덱스의 차	1	2	2	-1	-4

 

계산을 마치고 생각해보면 양수는 좌측으로 이동한 횟수, 음수는 우측으로 이동한 횟수를 의미하는 것을 알 수 있다.

하지만 우측으로 이동한 횟수는 고려할 필요가 없다. 한 번의 정렬을 시행할 때 좌측부터 비교를 시작하고 맨 우측부터 정렬이 완료된다는 것은 내부 for문을 한 바퀴 돌 때 한 원소당 좌측으로는 한 번만 이동할 수 있고, 우측으로는 여러 번 이동할 수 있다는 것을 의미 한다. 즉, 좌측으로 이동한 횟수가 우리가 원하는 정렬을 시행한 횟수이다. 

 

따라서 이전 인덱스에서 현재 인덱스를 뺀 값들 중 가장 큰 값을 구해주면 된다.

단, 문제에서 원하는 출력 답은 내부 for문을 한 번도 돌지 않아 flag를 세우는 1번의 횟수까지 카운팅해야 하기에 가장 큰 값 + 1 을 해주면 된다.