[99클럽/파이썬 챌린저/20일차] 소트

백준 1083번 소트 G4

 

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

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

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

 

 

그리디 알고리즘, 정렬

 

탐욕적인 방법으로 풀이할 수 있다.

현재 검색가능한 범위 내의 값 중 가장 큰 원소를 앞으로 옮기면 되는 문제이다.

 

s 값으로 인해 범위가 초과되지 않도록, s와 n 중 작은 범위를 택하였다.

사전 순으로 앞서기 위해, 가장 앞선 인덱스부터 검색을 진행한다.

 

import sys

n = int(sys.stdin.readline())
subs = list(map(int, sys.stdin.readline().split()))
s = int(sys.stdin.readline())

for i in range(n-1):
    if s <= 0: break
    max_either = max(subs[i+1:min(i+1+min(s, n), n)])
    if subs[i] > max_either: continue
    index = subs.index(max_either)
    s -= index-i
    for j in range(index, i, -1):
        subs[j], subs[j-1] = subs[j-1], subs[j]
        
print(*subs)

 

 

---