baekjoon. 1083 소트 [Gold V][python]

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

N = int(input())
numList = list(map(int, input().split()))
S = int(input())

swipe = 0
while (swipe < len(numList)):
    possibleMax = numList[swipe]
    possibleMaxIndex = swipe
    count = 0
    
    # swipe 다음부터 S번 횟수 내에서 가장 큰 숫자 찾기 
    ################ 
    for i in range(swipe + 1, len(numList)):
        # 횟수 넘어갔으면 넘어감 
        if (i - swipe) > S:
            break

        if numList[i] > possibleMax:
            possibleMax = numList[i]
            possibleMaxIndex = i
            count = i - swipe
     ################

    # swipe 할 수 있다면 swipe 
    ##################
    if (S - count) >= 0 and count > 0 :
        # print('check')
        del numList[possibleMaxIndex]
        numList.insert(swipe, possibleMax)

        S = S - count
	 ##################

    swipe += 1 

print(*numList)

 

처음읽고 나서는 bubble sort하면 끝이겠다 하고 풀었는데, 그게 아니었다. 

5
1 2 3 4 5
4

이 예시에서 문제가 원하는 답은 5 1 2 3 4 이고, bubble sort로 하면 2 3 4 5 1 이다. 

왜냐하면,  '이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.' 로 되어있기 때문에 S번 횟수 내에서 이동할 수 있는 가장 큰 수인 5가 맨 앞으로 나와야 한다. 

 

runtime error 반례>

7
70 60 50 40 30 20 10
1

>> 70 60 50 40 30 20 10

 

1% 반례 >

5
5 4 1 2 3 
50

>> 5 4 3 2 1

 

 

참고 풀이 > 

https://latte-is-horse.tistory.com/370

[solved.ac 골드5] 1083_소트 (파이썬, 정렬, 그리디)