[BOJ] 1083 - 소트 (Python)

 

 

아이디어

 

선택 정렬처럼 교환할 원소를 찾고, 거품 정렬의 교환 방법처럼 원소를 교환하며 내림차순 정렬한다.

 

 

풀이

 

앞에서부터 차례로 교환할 수 있는 범위 내 가장 큰 수를 찾고, 해당 원소를 앞쪽으로 이동시킨다.

 

def solution():
    N = int(input())
    A = list(map(int, input().split()))
    S = int(input())
    cnt = S
    for i in range(N-1):
        max_val = A[i]
        max_idx = i
        for j in range(i+1, min(i+cnt+1, N)):
            if A[j] > max_val:
                max_val = A[j]
                max_idx = j
        if max_idx > i:
            for j in range(max_idx, i, -1):
                A[j-1], A[j] = A[j], A[j-1]
            cnt -= max_idx-i
            if cnt <= 0:
                break
    print(*A)

solution()