백준 1083번 : 소트 (Python)

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

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

# 배열 완료된 숫자 개수
done = 0
# 이상적 배열
ideal = sorted(nums, reverse=True)
while s > 0 :
    if nums == ideal :
        break
    range_max = max(nums[done : min(n, done+s+1)])
    # print("배열 완료된 숫자 개수", done)
    # print("현 범위", nums[done : min(n, done+s+1)])
    # print("현 범위 최대", range_max)
    idx = nums[done:].index(range_max) + done
    # print("현 범위 최대의 인덱스 ", idx)
    if idx != done :
        nums.remove(range_max)
        nums.insert(done, range_max)
        s = s - (idx - done)
    done += 1
    # print("현 배열", nums)
    # print("남은 교환 수", s)
    
print(*nums, end=" ")

매 단계마다 검색 범위 내에서 가장 큰 숫자를 맨 앞으로 옮겨온다.

검색 범위는 맨 앞의 숫자부터 총 s+1 개의 숫자까지이다.

숫자 리스트 nums = [1, 3, 4, 2, 5], s = 3 인 테스트 케이스를 생각해보자.

[1, 3, 4, 2] 범위 내에서 가장 큰 수는 4이고, 따라서 4를 맨 앞으로 옮겨온다.

그럼 nums = [4, 1, 3, 2, 5]가 되고, 4를 옮겨오는데 4의 인덱스만큼의 교환(=2)을 했으므로 s = 1 이 된다.

다음 검색 범위는 이미 배치 완료된 수는 제외하므로 done이라는 변수에 그 개수를 저장한 후 인덱스들에 done만큼 더해준다.

즉 4를 넘어서 [1, 3] 범위에서 탐색해 3을 1 앞으로 옮겨오면 최종적인 배열은

[4, 3, 1, 2, 5]