[알고리즘/백준]1083 : 소트(python)

처음에는 앞에서 순회하면서 인접한 숫자들을 비교하는 버블 정렬인 줄 알았다.
사전 순으로 가장 뒷서는 것은 수가 클수록 뒤에 위치한다. 따라서 이동 횟수 안에서 가장 큰 수를 맨 앞으로 가져오면 된다.

1. 맨 앞에서 s 범위 안에서 가장 큰 수 찾기
2. 가장 큰 수가 맨 앞에 있으면 한 칸 뒤로 밀어서 다시 큰 수 찾기
3. 맨 앞이 아니면 s를 큰 수 인덱스 - 맨 앞 인덱스 한 값을 빼주기
4. 옮기기

import sys

input = sys.stdin.readline


def max_n(inner_idx):
    tmp, idx = a[inner_idx], inner_idx
    for i in range(inner_idx + 1, min(n, inner_idx + s + 1)):
        if a[i] > tmp:
            tmp = a[i]
            idx = i
    return tmp, idx


n = int(input())
a = list(map(int, input().split()))
s = int(input())
for i in range(n - 1):
    max_Num, max_Idx = max_n(i)
    if max_Idx != i:
        del a[max_Idx]
        a.insert(i, max_Num)
        s -= (max_Idx - i)
print(*a)