[백준] 1377번: 버블 소트

백준 1377번: 버블 소트

문제에 제시된 C++코드는 배열을 돌면서 정렬이 완료되면 확인 작업을 몇 회 했는지 출력하는 코드입니다.

10 1 5 2 3

1 5 2 3 10 #1번

1 2 3 5 10 #2번

1 2 3 5 10 #3번, 바뀐 부분이 없으므로 break!

따라서 3을 출력해야합니다.

물론 이 코드를 그대로 사용하면 시간초과가나죠..
더 빨리 횟수를 찾는방법을 알아내야 합니다.

문제에 제시된 버블소트에는 특징이 있는데,
바로 작은 수가 왼쪽으로 이동할 때는 한 칸씩 밖에 움직이지 못한다는 것입니다.
매번 왼쪽과 오른쪽수만 비교해서 큰 수를 오른쪽으로 옮기를 작업을 진행하니, 작은 수들은 한 칸씩만 밀려나는식으로 이동하는거죠.
10 1 5 2 3
1 5 2 3 10
1 2 3 5 10
제시된 숫자 3을 보시면 한칸씩 이동하는 모습을 볼 수 있습니다!

따라서 최대 왼쪽 이동 횟수를 구하면 답을 쉽게 찾아낼 수 있습니다.

이동횟수를 구하기위해 기존 위치를 함께 저장해줍니다.

[(10, 0), (1, 1), (5, 2), (2, 3), (3, 4)]

그 다음에 정렬해주세요!

[(1, 1), (2, 3), (3, 4), (5, 2), (10, 0)]

현재위치와 이전위치를 비교합니다. (이전위치-현재위치)

[1, 2, 2, -1, -4]

여기서 최대값 2에서 마지막 확인 횟수 1을 더하면 정답인 3이 됩니다.

*전체코드입니다.

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for i in range(N):
    n = int(input())
    arr.append((n, i))
    
arr.sort()
diff = [0]*N
for i in range(N):
    diff[i] = arr[i][1]-i
print(max(diff)+1)