[BaekJoon] 1377 버블 소트 (Gold 2) - Python

문제

 

버블 소트 알고리즘을 다음과 같이 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

출력예시1)

3

 

입력예시2)

5
1
3
5
7
9

출력예시2)

1

---

코드

 

import sys
input = sys.stdin.readline

N = int(input()) # 원소 개수 출력
A = [(int(input()), i) for i in range(N)] # 원소를 인덱스 번호와 함께 저장

sorted_A = sorted(A) # A를 정렬한 리스트를 따로 저장
ans = [sorted_A[i][1] - A[i][1] for i in range(N)] # 결과 리스트에 두 리스트의 원소의 인덱스 차이 저장

# 버블정렬은 1 회 진행할 때 마다 가장 큰 원소가 맨 뒤로 이동한다.
# 정렬된 리스트와 정렬 이전 리스트의 인덱스 차이를 계산하면 최고 진행 횟수를 계산해낼 수 있다.
# 정렬 후 - 정렬 전 인덱스의 차이를 구했을 때, 음수면 뒤로, 양수면 앞으로 이동한 칸수가 나온다.
# ex)
# 정렬 전: (10, 0) (1, 1) (5, 2) (2, 3) (3, 4)
# 정렬 후: (1, 1) (2, 3) (3, 4) (5, 2) (10, 0)
# 정렬 후 - 정렬 전: 1 2 2 -1 -4
# 이중 최대값은 2이고, 버블정렬을 2회만 진행해도 된다는 이야기이다.
# 따라서 결과는 최대값 + 1로 3이다

print(max(ans) + 1) # 출력

---

실행 화면

---

채점 결과