버블 소트[백준 1377] - python

 

버블 소트가 배열의 원소 별로 사이클이 몇번 시행되어야 하는 지를 출력하는 문제다

하나의 숫자가 제위치로 가는 순간을 사이클 하나로 정의해보자

 

당연히 그냥 버블소트를 생으로 구현해서 출력하면 시간초과이다.

 

10 1 5 2 3 의 예시를 보면 10과 5에 대한 버블소트 사이클이 시행되어야 한다. 

정렬된 상태는 1이 되므로 두번 버블소트 사이클이 시행되면 결과는 3이 된다.

 

1 3 5 7 9가 입력으로 주어지면 1을 출력하면 된다.

 

정답 코드 먼저 살펴보자

n = int(input())

array = []
for i in range(n) :
  n = int(input())
  array.append((n, i))

sorted_array = sorted(array)

answer = 0
for i in range(n) :
  answer = max(answer, sorted_array[i][1] - i + 1)

print(answer)

 

버블 소트가 구현되는 과정을 한 사이클씩 살펴보자

10 1 5 2 3
1 5 2 3 10
1 2 3 5 10

9 7 5 3 1
7 3 5 1 9
3 5 1 7 9
3 1 5 7 9
1 3 5 7 9

 

정렬이 될때마다 정렬되지 않은 배열에서는 왼쪽으로 인덱스가 하나씩 이동하게 된다

9 7 5 3 1
7 3 5 1 9
3 5 1 7 9
3 1 5 7 9
1 3 5 7 9

위 예시를 보면 한 사이클이 끝나고 나서의 배열을 보면 정렬되지 않은 배열의 상태에서 

인덱스가 하나씩 왼쪽으로 이동하는것을 볼 수 있다

 

이 문제는 정렬된 배열과 정렬되지 않은 배열의 원소들의 인덱스를 비교해서 가장 큰 값을 출력해주면 된다

 

 

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

1377번: 버블 소트