백준 1377 파이썬 , 버블 소트 그리고 sys.stdin.readline()

백준 1377 : 버블 소트

문제

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

1377번: 버블 소트

 

백준 1377

 

답안 코드 :

import sys
input = sys.stdin.readline

N = int(input())
A = []
for i in range(N):
    A.append((int(input()), i))
Max = 0
sorted_A = sorted(A)
for i in range(N):
    if Max < sorted_A[i][1] - i:    # 정렬 전 index - 정렬 후 index 계산의 최댓값 저장하기
        Max = sorted_A[i][1] - i
print(Max + 1)

 

import sys

input = sys.stdin.readline

N = int(input())

A = []

for i in range(N):

    A.append((int(input()), i))

Max = 0

sorted_A = sorted(A)

for i in range(N):

    if Max < sorted_A[i][1] - i:    # 정렬 전 index - 정렬 후 index 계산의 최댓값 저장하기

        Max = sorted_A[i][1] - i

print(Max + 1)

 

생각 :

버블 정렬

버블 정렬

 

이 문제는 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.

N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있다. 안쪽 for문이 몇 번 수행됐는지 구하는 아이디어를 떠올려야 한다.

 

(책 "Do It 알고리즘 코딩테스트" 참고)

 

안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어 :

안쪽 루프는 1에서 n - j 까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행함.

특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻.

즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 될 듯.

 

손 풀이

마지막에 +1  의 이유는 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최대값에 1을 더하는 것 입니다.

 

**

# input()대신 sys.stdin.readline()을 사용하는 이유

 

# 한 두줄 입력받는 문제들과 다르게, 반복문으로 여러줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 발생할 수 있습니다. 대표적인 예시가 백준 BOJ 15552번 문제입니다.

# sys.stdin.readline()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아집니다.

 

 

정렬 알고리즘 

https://mkisos.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-%ED%80%B5-%EC%A0%95%EB%A0%AC-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC-%EA%B8%B0%EC%88%98-%EC%A0%95%EB%A0%AC