[백준/Gold2] Swift - 버블 소트

2025.05.07 기준 Gold2
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 <= 500,000 (50만 이하의 자연수)
• 둘째 줄부터 N개의 줄에 A[1] ~ A[N]이 주어짐.
• 0 <= A[i] <= 1,000,000인 정수 (100만)

입출력 예

N	A		answer
5	[10, 1, 5, 2, 3]		3
5	[1, 3, 5, 7, 9]		1

 

아이디어

주어진 C++의 버블소트 코드는 O(N^2)이므로 최대 250,000,000,000으로 시간초과가 발생한다.

 

 우선 버블 소트를 1회 진행해보자.

버블 소트가 1회 일어날 때 버블이 되는 원소(10)가 아닌 나머지 원소는 왼쪽으로 한 칸만 이동할 수 있다.

 

중간에 버블이 되는 원소가 바뀌는 경우에도 2와 3을 보면 정렬이 일어났음을 알 수 있다.

따라서 (A[i]의 처음 인덱스 번호 - A[i]의 정렬 후 인덱스 번호) 를 구하면 A[i]가 정렬되기까지 수행된 버블 소트의 횟수를 알 수 있다.

 

문제에서 주어진 C++ 코드는 swap이 한 번도 일어나지 않은 시점의 횟수를 출력하고 있으므로 버블 정렬이 일어난 횟수 + 1을 찾으면 된다.

 

즉, A[i]가 정렬되는데 필요한 버블 소트의 최대 횟수 + 1을 구해야한다.

 

풀이

- 처음 숫자를 입력받을 때 index 정보를 함께 저장한다.

- 내장 함수 sort()로 정렬 후, 기존 index와 offset의 차이를 구한다.

- 차이의 최댓값이 버블소트를 실행하는 횟수

// 버블 소트를 몇 번째에서 멈추어야 하는지 구하는 문제
// N <= 50만

import Foundation

let N = Int(readLine()!)!
var nums: [(Int, Int)] = []     // 입력 순서: 숫자

for i in 0..<N {
    nums.append((i, Int(readLine()!)!))
}

nums.sort { $0.1 < $1.1 }       // 숫자를 기준으로 정렬

var answer = 0
nums.enumerated().forEach {
    let move = $0.element.0 - $0.offset     // 각 숫자의 입력 위치 - 정렬된 위치를 구함
    answer = answer < move ? move : answer  // (버블 소트 횟수 = 입력 위치 - 정렬된 위치)이므로 최댓값은 버블 소트가 진행되는 횟수임
}
print(answer + 1)               // 문제에서 버블 소트가 필요없는 순간을 물어봤기 때문에 버블 소트의 횟수 + 1을 해주어야 함.