[BOJ] 백준 1517번 버블소트 (Java)

#1517 버블 소트

난이도 : 골드 1

유형 : 자료 구조 / 좌표 압축 / 세그먼트 트리 || 합병 정렬

1517번: 버블 소트

▸ 문제

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 횟수를 출력한다

 

문제 풀이  

📚 조건

• 배열의 크기 N ( 1<= N <= 500,000)
• 원소 범위 A[i] ( 0 <= |A[i]| <= 1,000,000,000)

버블 정렬 연산횟수를 구하는 문제이지만 버블 정렬을 사용해서는 안된다. 해당 문제의 N의 범위가 상당히 크므로 버블소트의 시간복잡도는 O(N^2)이기 때문에 시간초과가 발생한다.

 

버블 정렬

배열 [6 4 3 5 2 1]을 버블 정렬을 사용해서 오름차순 시켜보자.

초기 상태

 

버블 정렬은 배열 인덱스 0부터 선형탐색으로 n-1까지 움직여 정렬하는 방식으로 동작한다. 

원소6 연산횟수: 5

원소5,4 연산횟수 : 3

원소4 연산횟수 : 2

원소3 연산횟수 : 2

원소2 연산횟수 : 1

 

 

과정을 보면 원소들은 앞에 있는 원소들 중 자신보다 낮은 수의 만큼 연산하는 것을 알 수 있다.

• 원소 6은 {4,3,5,2,1}보다 크기 때문에 총 5번
• 원소 5는 {2,1}보다 크기 때문에 총 2번
• 원소 4는 {3,2,1}보다 크기 때문에 총 3번
• 원소 3은 {2,1}보다 크기 때문에 총 2번
• 원소 2는 {1}보다 크기 때문에 총 1번
• 원소 1은 0번

→ 연산 횟수는 총 13이다.

 

결국 버블 정렬 연산횟수는 자신보다 앞에 있는 수의 갯수를 세어주면 되는 것을 발견할 수 있다. 이 패턴을 이해했으면 이젠 세그먼트 트리로 해당 문제를 풀이할 수 있게 된다. 

 

세그먼트 트리

세그먼트를 이용해서 앞에 자신보다 큰 값이 몇개나 들어있는지 트리의 구조를 이용해서 구하면 O(logN)으로 탐색가능하다. 해당 N번 반복하면 되므로 총 O(NlogN)으로 로직을 짤 수 있다.

 

좌표 압축하기

원소 범위 A[i] ( 0 <= |A[i]| <= 1,000,000,000) 이기 때문에 트리 원소로 담기에는 너무 부담되는 크기이다. 그래서 해당 배열 원소에 index를 붙여줘서 N의 최대 크기인 50만으로 제한을 해준 다음에 트리에 담아 줄 것이다.

for(int i=0; i<n; i++) {
	elements[i] = Integer.parseInt(st.nextToken());
}
        
// <K, V> = <segment tree index, elements in queue (중복 값 처리)>
Map<Long, Queue<Integer>> pos = new HashMap<>();
for (int i = 0; i < n; i++) {
    pos.computeIfAbsent(elements[i], k -> new LinkedList<>()).offer(i);
}

idx	0	1	2	3	4	5
elements	6	4	3	5	2	1

 

elements배열을 오름차순으로 정렬해준다. 작은 수 부터 세그먼트 트리에 넣어주어야 자신보다 앞의 구간 [idx+1 ~ n-1]에 자신보다 작은 수가 몇 개 있는지 카운트할 수 있기 때문이다. 물론 역으로도 탐색이 가능하다.

 

1. 원소 1 카운트

먼저 원소 1보다 앞에 있는 수는 없으므로 카운트는 0이다. 그리고 원소 1의 elements의 위치는 5이므로 해당 위치에 트리 +1을 업데이트 해준다.

원소1 카운트 (원래 위치5)

 

 

2. 원소 2 카운트

원소 2의 위치는 4이므로 (4,5]의 구간에 수를 카운트해준다. 카운트 +1

그리고나서 4번 위치에 해당하는 트리를 업데이트 해준다. 중요한 건 카운트를 먼저 해주고나서 트리를 업데이트해줘야 한다.

원소2 카운트 (원래 위치 4)

 

 

3. 원소 3 카운트

원소 3의 위치는 2이므로 [3,5] 구간을 카운트해준 다음 트리를 업데이트 해준다. 카운트 +2  (3번노드)

원소3 카운트 (원래 위치 2)

3. 원소 4 카운트

원소 4의 위치는 1이므로 [2,5] 구간을 카운트해준 다음 트리를 업데이트 해준다. 카운트 +3 (5번, 3번노드)

원소 4 카운트 (원래 위치1)

 

3. 원소 5 카운트

원소 5의 위치는 3이므로 [4,5] 구간을 카운트해준 다음 트리를 업데이트 해준다. 카운트 +2 (7번, 13번노드)

 

원소 5 카운트 (원래 위치 3)

3. 원소 6 카운트

원소 6의 위치는 0이므로 [1,5] 구간을 카운트해준 다음 트리를 업데이트 해준다. 카운트 +5 (3번, 5번, 9번 노드)

원소 6 카운트 (원래 위치 0)

 

 

연산과정 테이블

elements order	idx	구간 (idx+1 ~ n-1)	연산횟수
1	5	6~5 0	0
2	4	5~5	+1
3	2	3~5	+2
4	1	2~5	+3
5	3	4~5	+2
6	0	1~5	+5

 

 

풀이 코드 (세그먼트 트리) - 2024.01 update 중복 요소 처리 

import java.io.*;
import java.util.*;

public class Main {

	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		long[] elements = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			elements[i] = Integer.parseInt(st.nextToken());
		}

		// <K, V> = <segment tree index, elements in queue (중복 값 처리)>
		Map<Long, Queue<Integer>> pos = new HashMap<>();
		for (int i = 0; i < n; i++) {
			pos.computeIfAbsent(elements[i], k -> new LinkedList<>()).offer(i);
		}

		long[] index = elements.clone();
		Arrays.sort(index);

		long[] tree = new long[getTreeSize()];
		long ans =0;
		for(int i=0; i<n; i++)	{
			int idx = pos.get(index[i]).poll();
			ans += sum(tree,0, n-1, 1, idx+1, n-1);
			update(tree, 0, n-1, 1, idx, 1);
		}
		System.out.println(ans);
	}
	
	static int getTreeSize() {
		int h = (int)Math.ceil(Math.log(n)/Math.log(2))+1;
		return (int)Math.pow(2, h);
	}
	
	static long sum(long[] tree, int start, int end, int node, int left, int right) {
		if(end < left || right < start ) return 0;
		if(left <= start && end <= right) {
			return tree[node];
		
		}
		
		int mid = (start+end)/2;
		return sum(tree, start, mid, node*2, left, right) + sum(tree, mid+1, end, node*2+1, left, right);
	}
	
	static void update(long[] tree, int start, int end, int node, int idx, int dif) {
		if(start == end ) {
			tree[node] = dif;
			return;
		}
		int mid = (start+end)/2;
		if(idx <= mid) update(tree, start, mid, node*2, idx, dif);
		else update(tree, mid+1, end, node*2+1, idx, dif);
		
		tree[node] = tree[node*2]+tree[node*2+1];
	}
	
}

 

 

합병 정렬

합병 정렬도 위와 같은 방식으로 로직을 설계해주면 O(NlogN)으로 버블 정렬의 연산횟수를 구할 수 있다.

 

주어진 배열을 모두 divide한 후 다시 merge하는 과정에서 elements[i] > elements[j] 앞에 자신보다 큰 수 있는 경우 그만큼 count해주면 된다.

합병 정렬로 버블 정렬 연산횟수 구하는 과정

 

 

풀이 코드 (합병 정렬)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static long ans;
	static long[] elements, sorted;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		elements = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			elements[i] = Integer.parseInt(st.nextToken());
		}
		
		sorted = new long[n];
		divide(0,n-1);
		System.out.println(ans);
		
		
	}
	static void divide(int low, int high) {
		
		if(low < high) {
			int mid = (low+high)/2;
			
			divide(low, mid);
			divide(mid+1, high);
			
			merge(low, mid, high);
		}
	}
	
	static void merge(int low, int mid, int high) {
		int i = low;  // 왼쪽 시작 인덱스 
		int j=  mid+1; // 오른쪽 시작 인덱스 
		int k = low; // sorted배열 인덱스
		
		while(i<= mid && j <= high) {
			if(elements[i] <= elements[j]){
				sorted[k] = elements[i];
				i++;
			}else { // elements[i] > elements[j] 앞에 자신보다 큰 수 있는 경우
				sorted[k] = elements[j];
				j++;
				ans += (mid+1-i); // 연산횟수 카운트
			}
			k++;
		}
		
		// 나머지 합병과정 처리
		while(i <= mid) {
			sorted[k] = elements[i];
			i++;
			k++;
		}
		
		while(j <= high) {
			sorted[k] = elements[j];
			j++;
			k++;
		}
		
		for(int m=low; m<high+1; m++) {
			elements[m] = sorted[m];
		}
		
	}
	
}