[백준] 1377번 - 버블 소트

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

 

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

 

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

정답을 출력한다.

 

풀이

import sys
input = sys.stdin.readline

N = int(input())
nums = []

for n in range(N):
    nums.append((int(input()),n))

save = sorted(nums)
answer = 0

for n in range(N):
    answer = max(answer,save[n][1]-n)

print(answer+1)

 

해설

• 버블소트를 몇번 도는지 묻는 질문이지만 버블소트를 수행하면 시간초과가 발생한다.
• 왼쪽으로 가장 많이 옮겨간 수의 옮긴 횟수를 구하면 된다.
• 저장할때 정렬 이전 인덱스를 함께 저장하는 방식
• Python의 input은 시간이 오래걸려서 sys 모듈을 사용해야만 풀 수 있다 ... ㅎㅎ