[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1083번 _ 소트

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

1083번: 소트

[문제]

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) 버블 정렬의 구현이다.

2) 횟수를 다 사용할 때까지 앞에서부터 가져올 수 있는 범위 내 최댓값을 가져온다.

 

n=int(input())
a=list(map(int, input().split()))
k=int(input())
i=0
while k>0 and i<n:
    m=a.index(max(a[i:i+k+1]))
    if m!=i: 
        a[m],a[m-1]=a[m-1],a[m];k-=1 
    else:i+=1 
print(*a)