[파이썬] 백준 1083 : 소트 (골드4)

[파이썬] 백준 1083 : 소트 (골드4)

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

---

풀이

방향성 생각

• 각 자리수 마다 남은 횟수 S에 대해서 Swap 가능한 범위가 주어진다.

• Swap 범위 내에서 해당 자리보다 큰 값이 주어지면 Swap을 반복한다.

• $N=50$이라 swap만 제대로 구현하면 시간적으로 문제될 일은 없다.

  
  

---

전체코드

N = int(input())
arr = list(map(int,input().split()))
T = int(input())

goal = sorted(arr,reverse=True)

# 해당 인덱스 a에서 앞으로 한칸 swap
def swap(array: list, a: int)->list:
    array[a],array[a-1] = array[a-1],array[a]
    return array

while T:

    # 처음부터 스왑이 불가능한 경우 break로 루프를 탈출한다.
    if arr == goal:
        break

    for i in range(N-1):
        temp_max = max(arr[i+1:i+1+T])
        if arr[i] < max(arr[i+1:i+1+T]):
            arr = swap(arr,arr.index(temp_max))
            T -= 1
            break
print(*arr)

코멘트

• 출력형식 잘 보기.