(Python/🥇2)백준알고리즘 1377 번: 버블 소트

 

문제 바로가기 

문제:

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

입력:

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다. 위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

출력:

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

풀이 : 

풀이를 보면 swap 이 몇번 일어나는지 이다.

 

위에 코드의 결과는 버블소트 몇번째 턴에 정렬이 다 되는지 확인하는 문제이다.

10,1,5,2,3 를 정렬한다면

 

10,1,5,2,3 

1,5,2,3,10 

1,2,3,5,10 

 

이렇게 3번이다.  원래는 2번이긴 한데 시작이 1이여서 그런거 같다.

 

근데 버블정렬 특성상 포문 한번에 1칸밖에 이동을 못한다

만약에 1 5 3 10 2 일때 바롬 다음 for 문에서 2가 1 다음으로 올 수 없다.

하지만 2가 1 옆으로 가야한다는 사실은 변하지 않는다. 즉 4번 이다

 

그러면 여기서 알수 있는것은 기존 자기의 인덱스와 변하고 나서의 인덱스가 가장 큰 값을 구해주면 된다.

 

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(sys.stdin.readline())
arr = [(i + 1, int(sys.stdin.readline())) for i in range(n)]
arr2 = sorted(arr, key=lambda x: x[1])
res = 0
for i in range(n):
    res = max(arr2[i][0] - i, res)
print(res)

 

처음에는 arr2.inndex 이런식으로 햇는데 index가 시간을 많이 잡아 먹는지 시간초과가 난다.

 

다음과 같이 튜플형식으로 위치를 저장하면 된다.

그리고 나서 제일 중요한

 

변경 전 위치 - 변경 후 위치를 빼주면 된다.