[백준/BOJ] gold5 - 1083번 소트 (Python)

▶1083 - 소트

백준 로고

▶문제

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

 

▶입력

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

 

▶출력

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

728x90

▶풀이

최댓값을 찾아서 가장 왼쪽으로 넣어주는 방식을 사용하기로 했다.

최댓값이 들어간 가장 좌측 index는 고정시키는 방식이다.

 

일단 i번째부터 s까지 떨어져 있는 max 값을 가지고 온다.

해당하는 값을 pop 해주고 i번째에 값을 넣어준다.

그다음 s를 (idx - i)만큼 빼준다.

max number가 그만큼 좌측으로 이동했기 때문이다.

 

만약 idx와 i가 같다면 굳이 pop, insert를 해줄 필요가 없기 때문에 continue 해준다.

n = int(input())
arr = list(map(int, input().split()))
s = int(input())

for i in range(n):
    num = max(arr[i : min(n, i + s + 1)])
    idx = arr.index(num)

    if idx == i:
        continue
    
    arr.pop(idx)
    arr.insert(i, num)
    
    s -= (idx - i)
    if s == 0:
        break

print(*arr)