[버블 정렬] 백준 - 1377번: 버블 소트 (파이썬)

https://www.acmicpc.net/problem/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이다.

출력

정답을 출력한다.

예제 입출력1

# 입력
5
10
1
5
2
3

# 출력
3

예제 입출력2 

# 입력
5
1
3
5
7
9

# 출력
1

 

---

선 요약하자면 버블 정렬이 끝난 시점의 인덱스 i 값을 구하는 문제이다.
N의 최대 범위가 500,000 이므로 직접 버블 정렬을 구현하여 풀이하면 시간 초과가 발생한다.

import sys
input = sys.stdin.readline

n = int(input())
A = [int(input().rstrip()) for _ in range(n)]

changed = False
def bubble_sort():
    global changed
    for i in range(1, n+1):
        changed = False

        for j in range(n-i):
            if A[j] > A[j+1]:
                changed = True
                temp = A[j]
                A[j] = A[j+1]
                A[j+1] = temp

        # swap이 한 번도 일어나지 않은 루프 위치
        if changed == False:
            print(i)
            break

bubble_sort()

문제의 버블 정렬을 파이썬으로 직접 구현한 코드이다. 이걸로 제출하면 당연히 시간 초과가 발생한다.
그렇다면 어떻게 풀어야 할까?
 

---

N의 최댓값이 500,500 이므로 O(n^2) 시간복잡도로 풀 수 없다.
여기서 생각할 수 있는 아이디어는 다음과 같다.

• 버블 정렬은 왼쪽에서 오른쪽으로 이동하면서 정렬을 수행한다.
  이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다.
  • 데이터의 정렬 전 인덱스와 정렬 후 인덱스를 비교해서 왼쪽으로 가장 많이 이동한 값을 찾으면 정렬이 끝난 시점을 알 수 있다.

예제를 그림으로 표현해보면 다음과 같다.

기존 리스트에서 10은 인덱스 0에 위치했으나, 버블 정렬을 거치고 난 후 인덱스 4로 이동하였다.

0(기존 인덱스) - 4(정렬 후 인덱스) = -4

오른쪽으로 4만큼 이동했으니 -4 라는 값이 나왔다.

이런식으로 각 원소의 이동한 값을 계산하고, 최댓값을 도출하면 인덱스 (3->1), (4->2) 로 이동한 2라는 값이 나온다.

이 최댓값을 구하는 코드를 구현해보자.

 

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

for i in range(n):
    A.append((int(input()), i))  # [(10, 0), (1, 1), (5, 2), (2, 3), (3, 4)]
sorted_A = sorted(A)  # [(1, 1), (2, 3), (3, 4), (5, 2), (10, 0)]

원소 개수 n개 만큼 A 리스트에 원소를 저장하는데, 이때 원본 인덱스를 값과 함께 튜플 형식으로 저장한다.

 

max = 0
for i in range(n):
    if max < sorted_A[i][1] - i:  # 정렬 전 인덱스 - 정렬 후 인덱스 계산의 최댓값 저장
        max = sorted_A[i][1] - i
        
print(max + 1)

(정렬 전 인덱스) - (정렬 후 인덱스)의 최댓값을 for문을 돌면서 구해야 하므로 max 변수를 선언한다.

그리고 가장 마지막 루프에는 swap이 일어나지 않고 인덱스 값만 증가한다. 이를 감안하여 max + 1로 출력한다.

 

정답 코드

import sys
input = sys.stdin.readline

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

for i in range(n):
    A.append((int(input()), i))
sorted_A = sorted(A)

max = 0
for i in range(n):
    if max < sorted_A[i][1] - i:
        max = sorted_A[i][1] - i

print(max + 1)