백준(boj) 파이썬 - 1377 번 : 버블 소트

문제 링크 : https://www.acmicpc.net/problem/1377

1377번: 버블 소트

일단 이 문제를 풀기 위해서는 버블정렬을 알아야했다. 그래서 버블정렬에 대해 먼저 정리해 보았다.

https://infinitt.tistory.com/228

버블 정렬 (bubble sort)

 

 

---

 

아래 코드는 문제에서 제시한 C++코드이다.

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

 

* 문제에 주어진 TastCase로 설명해보면

 버블정렬은 1회차가 끝날때마다 가장 큰수가 맨 뒤로간다.

버블정렬을 진행하다가, 정렬을 마친 시점에서 몇회차인지 + 1를 출력하며 break된다.

즉, 정렬이 완료된 시점의 i + 1 을 출력하게 된다.

여기까지 이해한뒤, 그냥 그대로 파이썬코드로 옮겼더니 시간초과가 난다.

버블정렬의 시간복잡도는 O( n² ) 이므로 25만의 시간복잡도이기 때문에 당연한 결과였다.

 

 

* 시간초과 없이 풀기 위해서

정렬 전의 요소들의 인덱스 값과, 정렬 후의 요소들의 인덱스 값을 비교해본다면, 버블정렬시에 몇단계를 거쳤는지 알 수 있었다.

예를들어서 3개의 요소를 가진 리스트로 설명해보면, 앞의 수가 요소, 뒤의 빨간색이 인덱스값이다.

 

• 5는 뒤로 2칸을 이동했다.
• 3은 앞으로 1칸을 이동했다.
• 1은 앞으로 1칸을 이동했다.

위의 사실들은 인덱스끼리(빨간 숫자끼리) 뺄셈을 해보면 음수인경우는 뒤로 이동, 양수인 경우는 앞으로 이동한 칸 수가 나온다.

그리고 그 값들의 최대값이 버블정렬이 몇회차까지 필요한지를 나타내게 된다. 위의 예에서는 +1이 최대값이다.

그렇다면 1회차만 버블정렬을 실행해도 정렬이 된다는 이야기이다.

이러한 원리를 이용하여 시간초과없이 문제를 해결할 수 있었다.

 

 

따라서 문제의 테스트케이스로 다시 확인해보면

+2가 최댓값이므로 더하기 1을 해주어서 +3을 출력하면 답이 된다.

 

---

개념만 안다면 코드구현은 어렵지 않았다.

 

* 파이썬 (python) 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    arr.append( (int(input()), i) )

sorted_arr = sorted(arr) 
answer = [] 

for i in range(n):
    answer.append(sorted_arr[i][1] - arr[i][1])

print(max(answer) + 1)