[백준] 1377번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1377번: 버블 소트

 

1. 문제 설명

2. 풀이과정

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

버블 정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 의미이다. 해당 경우에는 반복을 종료하여 시간 복잡도를 줄일 수 있다.

해당 문제의 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있기 때문에 다른 방법으로 문제에 접근해야 한다.

 

안쪽 for 문은 1에서 n - i까지 왼쪽에서 오른쪽으로 이동하며 swap을 수행하는데 이는 데이터가 안쪽 for 문에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 의미이다.

데이터의 정렬 전 index 값과 정렬 후 index 값을 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 문제를 해결할 수 있다.

 

기본으로 입력되는 값들을 정렬하고 각 데이터마다 정렬 전 index 값에서 정렬 후 index 값을 빼고 최댓값을 찾는다.

swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안하여 최댓값에 1을 더한다.

 

슈도코드

1. N(데이터 개수) 입력받기
2. A(데이터 리스트, 클래스를 데이터로 담는 리스트) 생성
3. for N만큼 반복 : A 리스트 저장 ([index, 값] 형식)
4. MAX(swap 수행 최대 횟수 저장) 초기화
5. A 리스트 정렬 (값을 기준으로 오름차순 정렬)
6. for N만큼 반복
7. A[i]의 정렬 전 index - 정렬 후 index 계산, 최댓값을 찾아 저장
8. 최댓값 + 1을 정답으로 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

A = list()
for i in range(N):
    A.append([i, int(sys.stdin.readline())])

MAX = 0
sort_A = sorted(A, key = lambda x : x[1])

for i in range(N):
    if (MAX < sort_A[i][0] - i):
        MAX = sort_A[i][0] - i

print(MAX + 1)