BOJ1517 버블 소트(Java)

Mieulchi·2026년 2월 11일

algorithm

목록 보기

26/33

https://www.acmicpc.net/problem/1517

태그 : 정렬, 세그먼트 트리, 분할 정복

풀이 1 : 세그먼트 트리

가장 쉽게 푸는 법 : 0번 인덱스부터 오른쪽 배열에서 더 작은 값들의 갯수를 센다.

N^2 -> 시간초과. 어떻게 정렬을 잘 해서 할 수 있나 고민을 해보았는데, 잘 떠오르지 않았다.

태그를 확인해보니 세그먼트 트리가 있었고,

https://www.acmicpc.net/problem/7578

이 문제의 아이디어가 떠올랐다.

인덱스 정보를 가지고 정렬한 후, 세그트리를 갱신하면서 더 작은 노드의 수를 세면 되겠다고 생각했다.

이런 식으로 정렬된 수의 인덱스에 선을 긋고, 교차점을 센다고 생각하면 된다..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	static int N;
	static long ans;
	
	static class Int {
		int num;
		int idx;
		public Int(int n, int i) {
			this.num = n;
			this.idx = i;
		}
	}
	
	static Int[] arr = new Int[500001];
	static int[] tree = new int[2000001];
	
	
	static void update(int node, int l, int r, int idx) {
		if (r < idx || l > idx) {
			return;
		}
		
		if (l == r && l == idx) {
			tree[node]++;
			return;
		}
		
		int mid = (l + r) / 2;
		update(node * 2, l, mid, idx);
		update(node * 2 + 1, mid + 1, r, idx);
		
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
	
	static int get(int node, int l, int r, int s, int e) {
		if (r < s || l > e) {
			return 0;
		}
		
		if (s <= l && r <= e) {
			return tree[node];
		}
		
		int mid = (l + r) / 2;
		return get(node * 2, l, mid, s, e) + get(node * 2 + 1, mid + 1, r, s, e);
	}
	
	static void solve() {
		for(int i = 1; i <= N; ++i) {
			ans += get(1, 1, N, arr[i].idx, N);
			update(1, 1, N, arr[i].idx);
		}
		
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		N = Integer.parseInt(br.readLine().trim());

		st = new StringTokenizer(br.readLine().trim());
		
		for(int i = 1; i <= N; ++i) {
			arr[i] = new Int(Integer.parseInt(st.nextToken()), i);
		}
		
		Arrays.sort(arr, 1, N + 1, (i1, i2) -> {
			if (i1.num == i2.num) {
				return i1.idx - i2.idx;
			}
			return i1.num - i2.num;
		});
		
		solve();

		System.out.println(ans);
	}
}

풀이 2 : 분할 정복

세그트리 태그를 보고 풀었지만, 풀고 보니 2초로 아슬아슬하게 통과했다.

분할 정복 태그가 있었고...merge sort에서 merge 시 왼쪽 배열에서 오른쪽 배열보다 큰 수의 갯수가

이 문제의 답이라는 걸 알게 되었다.

시간적으로도, 문제 제목으로도 이쪽이 정해라는 생각이 들었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	static int N;
	static long ans;

	static int [] arr = new int [500000];
	static int [] tmp = new int [500000];
	
	static void merge_sort(int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			merge_sort(left, mid);
			merge_sort(mid + 1, right);
			merge(left, mid, right);
		}
	}
	
	static void merge(int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int k = left;
		
        
		while(i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				tmp[k++] = arr[i++];
			}
			else {
            	//합칠 때 왼쪽 배열의 수가 오른쪽 수보다 크다면?
                //나머지 수들도 해당 j번보다 크니까 다 더해줌. 그리고 오른쪽 배열의 다음 수 확인
				ans += (mid - i + 1);
				tmp[k++] = arr[j++];
			}
		}
		
		while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }

        for (int t = left; t <= right; t++) {
            arr[t] = tmp[t];
        }
	}
	
	static void solve() {
		merge_sort(0, N - 1);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		N = Integer.parseInt(br.readLine().trim());

		st = new StringTokenizer(br.readLine().trim());
		
		for(int i = 0; i < N; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		solve();

		System.out.println(ans);
	}
}