[BOJ] 1377번: 버블 소트 (python)

문제 링크 : https://www.acmicpc.net/problem/1377

💡 해결 방법

• 버블 정렬 그대로 작성하면 시간초과 남
• 안쪽 for문에서 큰 수가 뒤로 밀리면서 반복될 때마다, 반대로 작은 수들은 한 칸씩 앞으로 밀림
  
• 마지막 정렬까지(=바깥 for문 반복), 작은 수들은 자꾸 앞으로 한 칸씩 이동 -> 이를 bool change로 보기
• sort() 이후 숫자별 인덱스 변화 확인하여 왼쪽으로 가장 많이 이동한 값이 정답이 됨
• 인덱스 비교 수월하게 하기 위해 입력받을 때 인덱스까지 함께 2차원 배열 형태로 저장 -> sort()하면 첫 번재 원소(입력값)으로 정렬됨
• 모두 정렬된 후 마지막 바깥 for문 한 번 더 돌기 때문에 +1

(정답코드 참조..)

📌 BubbleSort

• 알고리즘
  1. 비교연산 루프 범위 설정
  2. 두 원소 비교
  3. swap 필요하면 진행
  4. 2-3 반복
  5. 정렬된 영역 확인
  6. 정렬된 영역 빼고 1-5 반복
     ※ 4번에서 swap 한 번도 일어나지 않았다면 프로세스 종료
• 코드

for i in range(N-1):
    for j in range(N-i-1):
        if list[j] > list[j+1]:
            temp = list[j+1]
            list[j+1] = list[j]
            list[j] = temp

• 버블 정렬 시간복잡도 : O(n^2)
• python sort() 함수 시간복잡도 : O(nlogn)
  
  

🖥️ 코드

import sys

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

✏️ 알고리즘 분류

• 정렬