[백준/Python] 1377번: 버블 소트

문제

https://www.acmicpc.net/problem/1377

(요약) 아래 소스코드를 실행했을 때, 어떤 값이 출력되는지 맞추는 문제

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은 500,000보다 작거나 같은 자연수이다." 라는 조건이 있으므로, 시간제한이 1초인 해당 문제를 버블 정렬(최악의 경우, 시간복잡도 O(N^2))으로는 풀 수 없다.

따라서 처음에는 O(N log N)의 시간복잡도를 갖는 머지 소트를 구현해서 정렬 후의 idx가 정렬 전의 idx와 일치하는 경우를 찾아 출력하는 방식을 고려하였다. 하지만 직접 시뮬레이션 하는 것보다 더 좋은 방법이 있음을 알게 되어 해당 아이디어를 공유한다.

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;
    }
}

출력해야 하는 수 i 가 의미하는 것은 뭘까?
더 이상 changed가 일어나지 않는, 즉 이미 정렬된 상태에 이르렀음을 의미한다. 따라서 몇번째 패스(i) 직전에 이미 정렬이 완료되었는지를 구하면 되는 문제라고 이해할 수 있다.

이때 버블 정렬의 경우, 각 원소는 한 번에 한 칸씩만 이동(swap)할 수 있다. 이 특성을 활용하면 정렬 전 원소의 위치와 정렬 후 원소의 위치를 비교해서 가장 많은 칸을 이동한 원소의 칸 수를 통해, 몇 번의 패스동안 유의미한 정렬이 이루어졌는지를 파악할 수 있게 된다.

풀이

n = int(input())
lst = []

for i in range(n):
    num = int(input())
    lst.append((num, i))
sorted_lst = sorted(lst)

answer = 0
for i in range(n):
    answer = max(answer, sorted_lst[i][1] - i)

print(answer+1)

정렬 전 lst를 (num, 정렬 전 idx) 형태의 튜플로 저장한다.
이후 정렬된 sorted_lst의 idx와 정렬 전 idx의 차이의 최대값을 구한다.
이 값이 곧, 최대 몇 번의 Pass동안 유의미한 정렬이 이루어졌는지를 의미한다.