[버블 정렬] 버블 소트 (백준 1377)

 

 

문제는 C++언어로 작성되었지만 해석해보면 버블정렬 할 때 이중 for문을 돌게 되는데 안쪽 for문에서 순서 변화가 안생기는 루프가 몇번 째인지 출력하는 문제다. 

즉, 몇 번 for문을 돌면 제대로 정렬이 되는 건지 묻는 문제다. 

 

풀이 과정을 봤는데 두 가지가 잘 이해가 안됐다. 

 

(1) 왜 index의 차이의 최대값으로 몇 번 돌았는지를 알 수 있는가

(2) 왜 (sort 전 index) - (sort 후 index) 가 되어야 하는 가

 

 

(소스코드)

 

import sys
input = sys.stdin.readline

N = int(input())
A = list(enumerate([int(input()) for _ in range(N)]))

sorted_A = sorted(A, key=lambda x:x[1])

ans = 0
for i in range(N):
    ans = max(ans, sorted_A[i][0]-i)
print(ans+1)