[ BOJ 1838 ] 버블 정렬(Python)

문제

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

정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 구하는 문제다

문제 풀이

[틀린 코드: 도현이 코드 그대로 사용]

for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
    if (flag == 0) {
        break;
    }
}

태국이를 이기기 위해 도현이가 작성한 코드다.
버블 정렬로 앞에서부터 순차적으로 요소를 정리하다가
더 이상 정렬할 필요가 없을 때 i를 출력한다.
이 코드를 파이썬 코드로 작성해서 제출했다.

[결과]
시간 초과가 났다. 당연하다.
문제에서 주어진 요소의 개수는 500,000 개이고 위의 코드는 O(n^2) 이다.
그럼 연산의 양은 250,000,000,000 개로 주어진 2초내에 계산을 끝낼 수 없다.

[정답]
문제의 i가 의미하는 것을 생각해보면 쉽게 풀 수 있다.

i는 더 이상 정렬을 하지 않아도 되서 멈췄을 때, 몇번 정렬이 이루어졌는지를 의미한다.

버블 정렬은 정렬을 한번씩 할 때마다 가장 큰 값이 가장 뒤로 이동한다.
따라서 [뒤로 이동한 값] 중 [가장 많이 이동한 거리]를 찾으면 된다.

즉, [정렬 전 인덱스 - 정렬 후 인덱스 > 0] 인 값 중 가장 큰 값 을 찾으면 된다.

코드

import sys
from collections import defaultdict
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().rsplit()))

before = defaultdict(int)
for i,num in enumerate(a):
    before[num]=i

a.sort()

after = defaultdict(int)
for i,num in enumerate(a):
    after[num] = i

answer = 0
for num in before:
    minus = before[num] - after[num]
    if (minus > 0 and minus > answer):
        answer = minus

print(answer)