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

버블소트 방식을 사용해서 s번 인접 원소 교환을 하는데 이렇게 해서 내림차순으로 가장 큰 숫자 배열을 만드는 문제이다.

Python

1차 시도 - 실패

n = int(input())
arr = list(map(int, input().split()))
s = int(input())

chk = True
while s > 0 and chk:
  chk = False
  for i in range(n-1):
    if arr[i] < arr[i+1] and s > 0:
      arr[i], arr[i+1] = arr[i+1], arr[i]
      s -= 1
      chk = True
      
print(" ".join(map(str, arr)))

단순하게 내림차순으로 가장 큰 숫자배열이니까 내림차순인지 판단하다가 오름차순 만나면 교환하는 것을 s번 반복하자 라고 생각했다.

그리고 실패했다.

10
1 2 3 4 5 6 7 8 9 10
17

질문게시판에서 찾아본 결과 위 테스트케이스에서 실패했다.

시도 2

n = int(input())
arr = list(map(int, input().split()))
s = int(input())

idx = 0
while s > 0 and idx < n:
  localMax = max(arr[idx:min(idx + s + 1, n)])
  target = arr.index(localMax)
  
  for i in range(target, idx, -1):
    if s == 0:
      break
    arr[i], arr[i-1] = arr[i-1], arr[i]
    s -= 1
  idx += 1

print(' '.join(map(str,arr)))

전략을 0번부터 탐색하는 idx라는 변수를 두고, idx에서 s개 혹은 n번까지의 원소 중 최대값을 찾고 그것을 idx위치까지 스와핑으로 가져오는 방식으로 바꾸었다.
스와핑 횟수만큼 s에서 뺐고 s가 0보다 클 때까지 혹은 s가 너무 커서(s를 전부 쓰라는 조건은 없었기에)idx가 arr배열 끝에 닿을 때까지 반복했다.