BOJ 1083 - 소트

문제

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

 

 

풀이

그리디 문제다

 

사전 순으로 뒤에 서기 위해 왼쪽에서 오른쪽으로 갈수록 수가 작아져야 한다

왼쪽에서 오른쪽으로 순회한 인덱스를 기준으로 오른쪽에 있는 수 중 남은 s번을 교체해서 가져올 수 있는 최댓값을 매순간 바꿔주면 된다

 

연속된 수만 교체할 수 있는데, 이는 인덱스 차이가 남은 s 이하라면 바로 바꿀 수 있다는 것을 의미한다

- s가 3일 때 3과 5의 위치를 바꾼다 -> 5 3 1 2 4, s = 2

                    1과 4의 위치를 바꾼다 -> 5 3 4 1 2, s = 0

 

 

코드

python

n = int(input())
arr = list(map(int, input().split()))
s = int(input())
 
while True:
    sort_done = True
 
    for i in range(n):
        idx = i
        change_step = 0
 
        for j in range(n - 1, i, -1): # i의 오른쪽에서 최대값 찾기
            if arr[idx] < arr[j] and j - i <= s:
                idx = j
                sort_done = False
                change_step = j - i
        
        if idx != i: # 최대값 발견 후 정렬
            temp = arr[idx]
            del arr[idx]
            arr.insert(i, temp) 
            s -= change_step
 
    if sort_done:
        break
 
print(*arr)