처음에는 현재 위치의 수가 바로 다음 위치의 수보다 작을 경우 교체하는 연산을 s번 진행하는 방식으로 코드를 작성하였다. 테스트 케이스는 모두 통과했지만 오답 처리를 당했다. 우선 처음에 작성한 코드이다.

n=int(input())
a=list(map(int, input().split()))
s=int(input())
cnt=0
cur=0
while cnt<s and cur<n-1:
    if a[cur]<a[cur+1]:
        a[cur], a[cur+1] = a[cur+1], a[cur]
        cnt+=1
        cur=-1
    cur+=1
print(*a)

문제를 조금 잘못 이해하고 푼 것 같았다. 그래서 다시 한번 읽어보고 다른 사람들의 풀이도 조금 찾아보았다. 이 문제는 바로 다음 수만 비교하는 것이 아니라 현재 위치보다 뒤에 있는 수 중에서 가장 큰 수와 비교하는 방식으로 풀이해아만 성공할 수 있다는 것을 알 수 있었다.

• n을 입력받는다.
• 수의 배열 a를 입력받는다.
• s를 입력받는다.
• n-1번 반복하는 i에 대한 for문을 돌린다.
  -> 만약 s가 0이라면 반복문을 종료한다. (교환할 수 있는 횟수가 더 이상 없는 상태)
  -> 가장 큰 수를 저장하는 변수 mx에 a[i]를 대입하고 가장 큰 수의 인덱스를 저장하는 변수 idx에 i를 대입한다.
  -> i+1부터 n과 i+1+s 중 더 작은 수까지 반복하는 j에 대한 for문을 돌린다. 이는 교환할 수 있는 횟수이다.
  --> 만약 mx보다 a[j]가 큰 경우,
  ---> mx에 a[j]를 대입한다.
  ---> idx에 j를 대입한다.
  -> s에서 idx-i를 빼준다. 이는 교환을 완료한 만큼 빼주는 것이다.
  -> idx부터 i까지 1씩 감소하며 반복하는 i에 대한 for문을 돌린다.
  --> a[j]에 a[j-1]을 대입한다.
  -> a[i]에 mx를 대입한다.
• a 배열을 출력한다.

Code

n=int(input())
a=list(map(int, input().split()))
s=int(input())
for i in range(n-1):
    if s==0:
        break
    mx, idx=a[i], i
    for j in range(i+1, min(n, i+1+s)):
        if mx<a[j]:
            mx=a[j]
            idx=j
    s-=idx-i
    for j in range(idx, i, -1):
        a[j]=a[j-1]
    a[i]=mx
print(*a)