문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

전체 코드

import sys

from typing import List

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().split()))
count = int(sys.stdin.readline().rstrip())

# 기준 값
i = 0
while i < n - 1 and count > 0:

    target = arr[i]
    swap_index = i
    # 바꿀 값 (최대 값) 찾아 내기.
    # i+1 ~ n 범위와 i+1 ~ i+1+count 중 더 작은 값의 범위로 스캔한다.
    # count가 n-(i+1) 보다 크다면 전자 범위 만큼 스캔해야 하지만, 더 적을 경우에는 n까지 다 못보기에 후자 범위로 택하게 된다.
    for j in range(i + 1, min(n, i + 1 + count)):

        if target < arr[j]:
            target = arr[j]
            swap_index = j

    # 스왑해야 하는 만큼 개수 s를 줄인다.
    count -= (swap_index - i)

    temp = arr[swap_index]
    del arr[swap_index]
    arr.insert(i, temp)

    i += 1

for elem in arr:
    print(elem, end=' ')

예제

각각 맨 마지막 줄이 출력이다.

10
1 2 3 4 5 6 7 8 9 10
17

10 9 1 2 3 4 5 6 7 8 

10
1 2 3 4 5 6 7 8 9 10
18

10 9 2 1 3 4 5 6 7 8 

10
1 2 3 4 5 6 7 8 9 10
19

10 9 3 1 2 4 5 6 7 8 

10
1 2 3 4 5 6 7 8 9 10
20

10 9 4 1 2 3 5 6 7 8