[백준 1377번] 버블 소트 (Python3)

import sys
input = sys.stdin.readline

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

A.sort()
maxdiff = 0
for i in range(N):
  a,i1 = A[i]
  maxdiff = max(maxdiff,i1-i)

print(maxdiff+1)

아이디어를 떠올리기 살짝 어려웠던 문제였다.

 

중요한 포인트는 어떤 숫자가 정렬과정에서 앞으로 가는건 연산 한번에 몇번이고 할 수 있지만 뒤로 가는건 연산 한번에 단 한번밖에 하지 못한다는 것이다.

따라서 현재의 위치에서 정렬된 위치로 가는데 몇 번 뒤로 가야하는지의 최댓값을 계산하면 정답이 나온다.

 

이때 주의해야 할 점은 처음에 입력값을 튜플로 입력받아야 한다는 것이다.

그렇지 않고 인덱스값 따로 숫자 따로 저장할 경우 중복된 숫자를 입력받을 때 차이가 생기게 된다.

 

예를들어 입력값이 1 1 1 인 경우 이미 정렬된 상태이기 때문에 정답은 1이지만, 따로 튜플로 저장하지 않고 sort하는 경우 1(3) 1(2) 1(1) 이런 식으로 정렬해 버릴 수가 있게 된다.

 

 

오늘의 교훈) 버블 소트에 대해 알아보자