[Python] 백준 1377번 버블 소트

문제에 주어진 것과 유사하게 코드를 작성하면 시간초과가 발생한다.

import sys
input = sys.stdin.readline

n = int(input())
num = [0] * n
for i in range(n):
    num[i] = int(input())
cnt = 1

for j in reversed(range(n)):
    flag = False
    for i in range(n - 1):
        if num[i] > num[i + 1]:
            flag = True
            tmp = num[i]
            num[i] = num[i + 1]
            num[i + 1] = tmp
    if flag == False:
        print(cnt)
        exit()
    cnt += 1

 

버블 정렬을 통해 문제를 풀면 시간 초과가 발생하므로, 새로운 접근 방식이 필요하다.

해당 문제는 인덱스 번호를 이용하여 해결할 수 있다.

swap이 한 번 돌때 인덱스 번호는 +1이 되므로, 정렬 전 인덱스 번호와 정렬 후 인덱스 번호를 비교하면 swap이 발생한 횟수를 알 수 있다.

 

예를 들어, [10, 1, 5, 3, 4]의 배열이 주어졌을 때, 정렬을 완료하면 [1, 3, 4, 5, 10]의 배열이 된다.

이 둘의 인덱스 번호를 비교하자.

10: origin[0] -> sorted[4]

1: origin[1] -> sorted[0]

5: origin[2] -> sorted[3]

3: origin[3] -> sorted[1]

4: origin[4] -> sorted[2]

 

정렬전 인덱스에서 정렬 후 인덱스를 빼면  몇 회 이동했는지 알 수 있다. 3과 4가 2회 이동했으므로 최댓값이다.

10: 0 - 4 = -4

1: 1 - 0 = 1

5: 2 - 3 = -1

3: 3 - 1 = 2

4: 4 - 2 = 2

 

그 후 반복문이 실행되는 것을 고려하여 +1을 해준다.

# 버블 소트
# swap이 한 번도 일어나지 않은 구간을 찾으시오.
# 첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 값이 하나씩 주어진다. N은 500,000보다 작거나 같은 자연수이다.
# 정답을 출력하시오.

import sys
input = sys.stdin.readline

n = int(input())
origin = []
for i in range(n):
    origin.append((int(input()), i))
sorted = sorted(origin)
num = [0] * n

for i in range(n):
    num[i] = sorted[i][1] - i + 1

print(max(num))

배열을 저장할 때 인덱스 값도 함께 저장한다.

그러면 두 번째 for문에서 인덱스 값을 계산할 때, 정렬된 배열의 인덱스 값과 기존 인덱스 값을 모두 알 수 있다.