[TIL] 1377번 - 버블 정렬

1. 1377번 - 버블 정렬

import sys

N = int(sys.stdin.readline())
array = [[int(sys.stdin.readline()), i] for i in range(N)]
    
array.sort()
max = -sys.maxsize
for i in range(N) :
    t = array[i][1] - i
    if max < t :
        max = t
print(max+1)

이 문제는 버블 정렬시 완료되는 반복 횟수를 구하는 문제이다.
주어진 c++ 코드로도 답은 구할 수 있지만 시간초과가 발생했다.
즉, 이중 반복문을 제거할 수 있어야 한다.

위의 그림은 버블 정렬 과정을 써본 것이다.

버블 정렬은 맨 뒤에서 부터 큰 값이 먼저 정렬된다.

그러므로 정렬되지 않은 값 중 가장 큰 값은 오른쪽으로 계속 이동할 것이다.

큰 값과 비교된 작은 값들은 한번씩 왼쪽으로 이동될 것이다.

원래 인덱스 - 바뀐 인덱스 = 이동한 횟수

양수 = 왼쪽으로 이동한 횟수

음수 = 오른쪽으로 이동한 횟수

우리가 구해야 할 값은 오른쪽으로 이동된 횟수가 아닌 왼쪽으로 이동된 횟수이다.

그러므로 이동한 횟수가 가장 큰 값을 구하면 된다.

이때 주의할 점은 한번도 이동을 안해도 1이 되어야 하므로 구한 횟수에 1을 더해주어야 한다. 

---

오늘은 아침에 문제풀이한 내용이 매우 인상깊어서 적어본다.

처음에는 막막했는데 생각하다가 인덱스를 사용하겠다는 생각이 들어서 시도했지만

음수와 양수를 구분하는 이유까지 생각을 못해서 실패한 문제였다.

비록 완벽하게 혼자 푼것은 아니지만 어느 정도 풀이에 접근했다는 것을 느끼면서 성장한 느낌을 받았다.

앞으로도 꾸준히 준비하자!