설명
N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.
버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.
입력
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.
출력
첫째 줄에 Swap 횟수를 출력한다
예시 입력
예시 출력
3
3 2 1
JavaScript
복사
3
JavaScript
복사
풀이 과정
문제 설명에 앞서 버블 소트에 대해 간략하게 설명하겠습니다.
버블 소트란?
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 소트라는 이름이 지어졌습니다. 버블 소트는 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
예제를 통해 설명해보겠습니다.
5 4 3 2 1 을 오름차순으로 정렬하고자 합니다.
이 때, 어떤 과정을 거치고 몇 번의 swap이 일어날까요?
(1) 4 5 3 2 1 (2) 4 3 5 2 1 (3) 4 3 2 5 1 (4) 4 3 2 1 5 (5) 3 4 2 1 5
(6) 3 2 4 1 5(7) 3 2 1 4 5 (8) 2 3 1 4 5 (9) 2 1 3 4 5 (10) 1 2 3 4 5
그렇다면 정렬이 발생할 때 마다 count를 증가하면 쉽게 구할 수 있지 않을까요?
버블 소트를 간단하게 구현해봅시다.
public void bubbleSort(){
int [] arr = new int [] {5,4,3,2,1};
int count = 0;
for(int i = 0; i < arr.length; i++){
for(int j = i+1; j <arr.length; j++) {
if (arr[i] < arr[j]){
swap(arr[i], arr[j]);
count++;
}
}
}
}
Java
복사
알고리즘 스터디 8개월 짬밥의 여러분들은 쉽게 눈치채셨겠지만 O(n^2) 인 것을 확인할 수 있습니다.
그렇다면 어떻게 해결해야될까요?
머지 소트를 사용하자
“버블 소트로 구현하라고 했는데 머지 소트? 이거 완전 날먹 아닌가요? (김소연, 소프트 20)”
머지 소트는 정렬을 분할 정복으로 구현한 것입니다. 이 문제에서 중요한건 어떻게 정렬하는가가 아닌, 머지 소트로 정렬할 때 어떻게 swap 횟수를 기록할 것인가 입니다.
핵심은 “자기 보다 큰 수의 개수 만큼 count를 더한다” 입니다.
최종 코드
package baekjoon.divide_and_conquer;
import java.io.*;
import java.util.StringTokenizer;
public class _1517 {
static long answer;
static long[] A, B;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
A = new long[N];
B = new long[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
divide_conquer(0, N - 1);
System.out.println(answer);
}
static void divide_conquer(int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
divide_conquer(low, mid);
divide_conquer(mid + 1, high);
merge(low, mid, high);
}
}
static void merge(int low, int mid, int high) {
int leftIndex = low;
int rightIndex = mid + 1;
int index = low;
while (leftIndex <= mid && rightIndex <= high) {
if (A[leftIndex] <= A[rightIndex]) {
B[index] = A[leftIndex];
leftIndex++;
} else {
B[index] = A[rightIndex];
rightIndex++;
answer += (mid + 1 - leftIndex);
}
index++;
}
while (leftIndex <= mid) {
B[index] = A[leftIndex];
leftIndex++;
index++;
}
while (rightIndex <= high) {
B[index] = A[rightIndex];
rightIndex++;
index++;
}
for (int i = low; i < high + 1; i++) {
A[i] = B[i];
}
}
}
JavaScript
복사
