문제
N개의 수로 이루어진 수열에서 버블 소트를 수행할 때 swap이 몇 번 일어나는지 구하는 문제이다. 버블 소트에서 swap 횟수는 배열 내의 역순 쌍(inversion pair)의 수와 동일하다. N이 최대 500,000이므로 O(N²) 버블 소트를 직접 실행하면 시간 초과가 발생한다.
입력
- 첫째 줄: N (1 이상 500,000 이하)
- 둘째 줄: N개의 수 (0 이상 1,000,000,000 이하 정수)
출력
- 버블 소트 수행 중 swap이 일어나는 횟수
예제
| 입력 | 출력 |
|---|---|
3 3 2 1 | 3 |
풀이
병합 정렬(Merge Sort)을 이용하여 역순 쌍의 수를 O(N log N)에 계산한다. 병합 과정에서 오른쪽 배열의 원소가 왼쪽 배열 앞에 놓일 때마다 역순 쌍이 발생한다.
- 배열을 절반으로 나누어 재귀적으로 정렬한다(
divide함수). - 병합(
merge) 단계에서 왼쪽 포인터 i와 오른쪽 포인터 j를 비교한다. arr[j] < arr[i]이면 오른쪽 원소가 먼저 삽입되며, 이때 왼쪽에 남아 있는 원소 수(mid+1-i)만큼 역순 쌍이 발생한다.- 역순 쌍 수를 전역 변수
ans에 누적하고, 정렬이 완료되면 출력한다.
핵심 아이디어: 버블 소트의 swap 횟수 = 역순 쌍(inversion) 수이다. 병합 정렬의 병합 단계에서 오른쪽 원소가 앞으로 올 때, 왼쪽에 남은 모든 원소와 역순 관계가 되므로 그 개수를 한 번에 더할 수 있다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day105BOJ1517버블솔트머지솔트 { // 1517 제목은 버블솔트인데, 버블솔트 쓰면 안됨.
static int N;
static long ans;
static long[] arr, tmp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new long[N];
tmp = new long[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
divide(0, N - 1);
System.out.println(ans);
br.close();
}
static void divide(int st, int ed) {
if (st < ed) {
int mid = (st + ed) / 2;
divide(st, mid);
divide(mid + 1, ed);
merge(st, mid, ed);
}
}
static void merge(int st, int mid, int ed) {
int i = st, j = mid + 1, idx = st;
while (i < mid + 1 && j < ed + 1)
if (arr[i] <= arr[j])
tmp[idx++] = arr[i++];
else {
tmp[idx++] = arr[j++];
ans += (mid + 1 - i);
}
while (i < mid + 1)
tmp[idx++] = arr[i++];
while (j < ed + 1)
tmp[idx++] = arr[j++];
for (int n = st; n < ed + 1; n++)
arr[n] = tmp[n];
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)