[코테] 백준 그리디 1083번 문제

1083번 : 소트

문제 링크

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

문제 설명

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

입력

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

출력

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

문제 풀이

# 변수 입력
N = int(input())
arr = list(map(int, input().split()))
S = int(input())

sorted_idx = 0

# 남은 교환 횟수가 0보다 크고, 다 정렬되기 전까지 반복
while S > 0 and sorted_idx < N : 
    # 최댓값 index 얻기
    idx = arr.index(max(arr[sorted_idx:min(N, sorted_idx + S + 1)]))
    
    # 최대값이 sorted_idx 자리에 오지 않을 때
    if idx != sorted_idx :
        arr[idx-1], arr[idx] = arr[idx], arr[idx-1]
        S -= 1
        
    # 최대값이 sorted_idx 자리에 오면 sorted_idx + 1
    else : 
        sorted_idx += 1

print(*arr)