BOJ 1377번: 버블 소트

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

1377번: 버블 소트

처음엔 문제에 나와있는 코드를 그대로 구현해봤는데, 시간초과가 났다. 버블정렬은 O(n^2)의 시간복잡도를 가지기 때문이다.

import sys

N = int(sys.stdin.readline())
A = [-1]
for _ in range(N):
    A.append(int(sys.stdin.readline()))

for i in range(1, N+2):
    change = False
    for j in range(1, N-i+1):
        if (A[j] > A[j+1]):
            change = True
            A[j], A[j+1] = A[j+1], A[j]

    if (change==False):
        print(i)
        break

검색을 통해 힌트를 좀 얻었는데, 버블 정렬은 한 번 훑으면서 A[j]>A[j+1]인 A[j+1]가 앞으로 한 칸씩 swap 된다.

따라서 정렬 후의 인덱스와 정렬 전의 인덱스를 비교해서 차이가 가장 큰 수만큼 i가 늘어났다고 생각할 수 있다.

import sys

N = int(sys.stdin.readline())
A = []
for i in range(N):
    a = int(sys.stdin.readline())
    A.append([a,i])

A.sort()
ans = 0
for i in range(N):
    tmp = A[i][1] - i
    ans = max(ans, tmp)

print(ans+1)