문제 분석
버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.
'버블 정렬의 이중 for 문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 것을 의미한다.
해당 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있다. 따라서 안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요하다.
안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어
안쪽 루프는 1에서 n-i까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다.
이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있다.
소스 코드
# 버블 소트
import sys
input = sys.stdin.readline
N = int(input())
arr = []
for i in range(N):
arr.append((int(input()), i))
Max = 0
sorted_arr = sorted(arr)
for i in range(N):
if Max < sorted_arr[i][1] - i:
Max = sorted_arr[i][1] - i
print(Max + 1)리스트에 튜플 형태로 값을 저장해서 저장한 값의 인덱스를 알 수 있게 처리하였습니다.
