[Do it! 알고리즘] 버블 정렬 프로그램1(백준 1377)

Do it! 알고리즘 코딩테스트 책

04. 버블 정렬 프로그램1(백준 1377번)

처음에 있던 인덱스와 최종적으로 바뀐 인덱스와의 차이중에서 가장 큰 값에 1을 더하면 됨.

코드

import sys
input = sys.stdin.readline

N = int(input())  # 입력 개수
A = []

for i in range(N):
    num = int(input())
    A.append((num, i))  # 각 숫자와 원래 인덱스를 튜플로 저장

# 숫자를 기준으로 정렬하되, 원래 인덱스 정보를 유지
sorted_A = sorted(A)

result = 0
for i in range(N):
    result = max(result, sorted_A[i][1] - i)

print(result + 1) 

References

• Do it! 알고리즘 책
• https://www.acmicpc.net/problem/1377