[BaekJoon] 1838 버블 정렬 (Gold 2) - Python

문제

 

버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개의 서로 다른 정수가 A[0], A[1], ..., A[N-1]의 정수형 배열에 저장되어 있고, 이를 오름차순으로 정렬하기 위해 태국이는 다음과 같은 코드를 작성하였다.

for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
}

하지만 주어진 배열 A에 따라 변수 i가 모든 loop를 반복하지 않아도 정렬이 완료되기도 한다. 따라서 도현이는 다음과 같이 코드를 개선하였다.

for (i=0; i<N; i++) {
    flag = 0;
    for (j=0; j<N-1; j++) {
        if (A[j] > A[j+1]) {
            flag = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
    if (flag == 0) {
        break;
    }
}

도현이는 자신이 태국이보다 우월하다는 것을 증명하기 위해, 개선된 코드를 이용하여 주어진 배열 A를 정렬해 보려고 한다. 만일 정렬이 완료되었을 때(즉 for문을 빠져나왔을 때)의 i값이 작으면 작을수록 도현이의 코드가 더 빠른 것이 된다. 태국이를 이기고 싶은 도현이를 도와서, 배열 A에 저장된 수가 주어지면 정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 구하는 프로그램을 작성하시오.

---

입출력 예시

 

입력: 첫째 줄에는 정수 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다. 주어지는 정수는 절댓값이 2,147,483,647을 넘지 않는다.

출력: 첫째 줄에 정렬이 완료되었을 때 변수 i에 저장되어 있는 값을 출력한다.

 

입력예시1)

5
30 10 44 27 49

출력예시1)

2

---

코드

 

도현이의 코드를 그대로 파이썬으로 작성하여 제출했더니,,,,

시간 초과 나오더라구요,,,,

 

도현이 코드에서 i가 뭔지만 잘 생각해보믄

정렬이 몇 번 진행되었는지를 나타내요

그래서 정렬이전 인덱스 - 정렬 이후 인덱스가 가장 큰 값이 i가 된답니다 후후

 

N = int(input()) # N입력
A = list(map(int, input().split())) # 숫자 리스트 입력

X = dict() # 정렬 이전 인덱스 저장을 위한 딕셔너리 생성
for i, num in enumerate(A): X[num] = i # 정렬 이전 인덱스 저장

A.sort() # A 정렬

Y = dict() # 정렬 이후 인덱스 저장을 위한 딕셔너리 생성
for i, num in enumerate(A): Y[num] = i # 정렬 이후 인덱스 저장

ans = 0 # 결과값
for num in X: # 반복문을 통해 정렬이전 인덱스 - 정렬 이후 인덱스 값 중 가장 큰 값 구하기
    buf = X[num] - Y[num]
    if buf > 0 and buf > ans: ans = buf

print(ans) # 결과값 출력

---

실행 화면

 

---

채점 결과