백준 1377 [버블 소트] 파이썬

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

1377번: 버블 소트

# 백준 1377 버블 소트
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
lst = {}
lst_sorted = []
lst_val = []
answer = -1
diffs = defaultdict(lambda: 1000001)
for i in range(N):
    K = int(input())
    lst[K] = i
    lst_sorted.append(K)
lst_sorted.sort()
for i in range(N):
    diff = min(abs(lst[lst_sorted[i]]-i), N-i-1)
    diffs[lst_sorted[i]] = min(diffs[lst_sorted[i]], diff)

for diff in diffs.values():
    answer = max(answer, diff)
print(answer+1)

먼저 lst에 각 원소의 index값을 저장한다. (정렬 전 index)

그리고 lst_sorted에는 정렬 한 값을 저장한다.

중복된 값이 존재할 수 있으므로, diffs 딕셔너리를 생성한다.

 

문제에서 반복문을 도는 조건은 k번째 수가 k+1 번째 수보다 클때 (정렬이 완전히 되지 않았을 때)이므로, 

diff= min ( | 정렬된 자신의 index- 정렬되지 않았을 때 index | , 자기 자신이 알맞게 정렬됐을 순서) 이다.

즉, diff는 자신 앞에 있는 인덱스의 수가 뒤로가서 정렬 되거나, 자기가 뒤로가서 정렬되는 경우의 수를 따져서 더 작은 값을 저장한다.