[백준] 1083 소트

문제 링크

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

문제 설명

• 문제가 짧지만 자세히 봐야 한다.
  • 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.
• 소트한 결과가 사전순으로 가장 뒷서는 것을 출력하라는 의미는 가장 내림차순 정렬이 된 것을 의미한다.
• 연속된 숫자만 교환 가능 하다고 했으니 배열내에서 가장 큰 값이 가장 앞쪽으로 이동하는데 걸리는 횟수를 사용한다.
• 이동 횟수는 S번으로 제한된다. 따라서 nums 배열의 가장 큰 값을 찾을 때에는 이동횟수가 가능한 범위 내에서 찾아야 한다.
• 왜 그리디인지?
  • 이 문제는 자릿수를 바꿔서 가장 큰 숫자를 만드라는 문제와 유사하게 생각할 수 있다. 따라서 이동할 수 있는 범위 내에서 가장 큰 숫자를 앞쪽으로 이동시키는 식으로 문제를 해결하면 가장 큰 자리수에 올 수 있는 가장 큰 수가 오게 되고 다음번 숫자로 어떤 것을 골라도 그전의 선택에 영향을 미치지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달해도 최적해임이 보작된다.

코드

import sys

n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
s = int(input())
new = []

temp = s
while temp > 0 and len(nums) > 0:
    max_index = nums.index(max(nums[:temp + 1]))
    new.append(nums.pop(max_index))
    temp = temp - max_index

print(*(new + nums))