[ BOJ 1377 ] 버블 소트(Python)

문제

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

1838 버블 정렬 과 똑같은 문제다.
입력을 받는 부분과 배열이 1번방부터 채워지는 점만 다르다.

문제 풀이

(정렬 전 인덱스 - 정렬 후 인덱스 > 0) 인 값 중 가장 큰 값을 찾아주면 된다.

코드

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

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

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+1)