백준 [ALGORITHM] - 버블 소트 (1377)

import sys
from queue import PriorityQueue

input = sys.stdin.readline

n = int(input())
arr = []
ans_arr = []

for i in range(n):
    arr.append((int(input()),i))

arr_sorted = sorted(arr)

for i in range(n):
    ans = arr_sorted[i][1] - i
    ans_arr.append(ans)
    #print(ans)
    
print(max(ans_arr)+1)

요즘 다시 알고리즘을 매일 공부하고 있는데, 이 문제 풀면서 재밌는걸 하나 배워서 메모겸 글을 남긴다.

해당 문제 설명에서 준 코드로 python에서 구현해서 마지막으로 swap이 되지 않은 루틴 번호를 구하려면 시간이 한참 초과된다.

일단 python의 기본함수 중 sort를 이용해서 처음 입력된 배열 data와 처음 인덱스를 튜플로 arr에 저장하고, arr을 sort한다.

그리고 sort된 튜플의 초기 index값에다가 지금 index를 뺀 값중 가장 큰 값을 구하면 그게 곧 가장 마지막으로 swap이 일어난 루틴 횟수이기 때문에 시간을 초과하는 기존의 버블정렬을 수행해서 구하는 방법을 사용하지 않고도 풀 수 있다.