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

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

1. 문제 해결 과정

n의 크기가 500,000이기 때문에 버블 정렬 알고리즘을 코드로 구현해 풀면 시간초과가 발생한다.(버블 정렬은 O(N^2))

 

따라서 index를 이용한 아이디어를 이용해 문제를 풀어야한다.

 

오른쪽에 작은 수가 있는 경우, 한 번의 loof에서 1만큼의 인덱스가 왼쪽으로 이동한다.

 

이 경우에 (정렬 전 index) - (정렬 후 index)를 하면 양수가 나오게 된다.

 

따라서 정렬 전 index - 정렬 후 index 의 max + 1(정렬이 다 되었는데 loof를 한 번 더 돌 때를 더해줌)을 출력해주면 된다.

 

 

아래는 참고한 블로그 

 

https://infinitt.tistory.com/229

백준(boj) 파이썬 - 1377 번 : 버블 소트

 

2. 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())

num = []

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

num.sort()

max_cnt = 0

for j in range(n):
  max_cnt = max(num[j][1] - j, max_cnt)
  
print(max_cnt+1)