728x90
1517 - 버블 소트
https://www.acmicpc.net/problem/1517

문제
N개의 수로 이뤄진 수열 A[1], A[2], ..., A[N]
버블 소트: 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방식
ex. 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3
입력
첫째 줄: N (1 <= N <= 500,000)
다음 줄: N개의 정수 A[1], A[2], ..., A[N] (0 <= |A[i]| <= 1,000,000,000)
출력: swap 횟수
풀이
버블 정렬에서 발생하는 swap 횟수 = 역순 쌍(inverse) 개수
합병 정렬(Merge Sort)
배열을 반으로 분할 -> 각 절반을 재귀적으로 정렬 -> 정렬된 두 배열 병합(merge)
시간 복잡도: O(N log N)
mergeSort(lt, rt)
- [lt ~ rt] 구간 정렬
- `lt >= rt`: 원소가 1개 이하 => 이미 정렬된 상태
- 왼쪽, 오른쪽 반으로 나누고 각각 정렬한 뒤 `merge()`로 합침
static void mergeSort(int lt, int rt) {
if (lt >= rt) return;
int mid = (lt + rt) / 2;
mergeSort(lt, mid);
mergeSort(mid + 1, rt);
merge(lt, mid, rt);
}
merge(lt, mid, rt)
- i: 왼쪽 배열 포인터 / j: 오른쪽 배열 포인터 / `idx`: 임시 배열(`tmp`)에 넣을 위치
- [lt ~ mid], [mid + 1 ~ rt] 이미 정렬됐다는 전제
- 왼쪽, 오른쪽 배열 둘다 남아 있을 때만 비교
- 정상 정렬 케이스: `A[i] <= A[j]` -> `tmp[idx++] = A[i++]`
- 역순 쌍 O (`A[i] > A[j]`) -> 왼쪽 배열 이미 정렬됐고 전부 A[j]보다 큼
=> `A[j]`가 왼쪽 원소들 전부와 swap 해야 함
- `tmp[idx++] = A[j++]`
- `cnt += (mid - i + 1)`
- 남은 값 처리
- 오른쪽 배열 먼저 끝난 경우: `i <= mid` -> `tmp[idx++] = A[i++]`
- 왼쪽 배열 먼저 끝난 경우:`j <= rt` -> `tmp[idx++] = A[j++]`
- 원본 배열에 복사
static void merge(int lt, int mid, int rt) {
int i = lt;
int j = mid + 1;
int idx = lt;
while (i <= mid && j <= rt) {
if (A[i] <= A[j]) tmp[idx++] = A[i++];
else {
tmp[idx++] = A[j++];
cnt += (mid - i + 1);
}
}
while (i <= mid) tmp[idx++] = A[i++];
while (j <= rt) tmp[idx++] = A[j++];
for (int k = lt; k <= rt; k++) A[k] = tmp[k];
}
코드
import java.io.*;
import java.util.*;
// 버블 소트
public class boj_1517 {
static int N;
static int[] A, tmp;
static long cnt = 0;
static void mergeSort(int lt, int rt) {
if (lt >= rt) return;
int mid = (lt + rt) / 2;
mergeSort(lt, mid);
mergeSort(mid + 1, rt);
merge(lt, mid, rt);
}
static void merge(int lt, int mid, int rt) {
int i = lt;
int j = mid + 1;
int idx = lt;
while (i <= mid && j <= rt) {
if (A[i] <= A[j]) tmp[idx++] = A[i++];
else {
tmp[idx++] = A[j++];
cnt += (mid - i + 1);
}
}
while (i <= mid) tmp[idx++] = A[i++];
while (j <= rt) tmp[idx++] = A[j++];
for (int k = lt; k <= rt; k++) A[k] = tmp[k];
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
A = new int[N];
tmp = new int[N];
StringTokenizer st = new StringTokenizer(in.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
mergeSort(0, N - 1);
System.out.println(cnt);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DFS] 백준 3109 - 빵집 (Java) (0) | 2026.01.13 |
|---|---|
| [BOJ/Simulation] 백준 17143 - 낚시왕 (Java) (1) | 2026.01.12 |
| [BOJ/BFS] 백준 16946 - 벽 부수고 이동하기 4 (Java) (0) | 2026.01.12 |
| [BOJ/DP] 백준 2342 - Dance Dance Revolution (Java) (0) | 2026.01.12 |
| [BOJ/BFS] 백준 2146 - 다리 만들기 (Java) (0) | 2026.01.05 |