백준 1517번 자바 ☆

문제

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

1517번: 버블 소트

1. 버블소트를 가장한 머지소트 문제

문제 제목이 버블소트라고 버블소트로 풀었다 당연스럽게 시간초과로 틀렸다. 머지 소트로 풀어야 통과가 된다.

https://ahlight.tistory.com/79

백준 2751번 자바

머지소트에 대해 간략히 정리하며 풀었던 문제다.

머지소트의 원리만 이해한다면 그렇게 어렵지 않게 풀 수 있다. 

예를 들어, 아래와 같이 2개로 구분된 배열이 각 구간의 첫번째 인덱스부터 비교를 시작해서 정렬을 한다.

<temp 배열>

2

3

4

5

1

6

7

8

아래와 같이 arr 배열엔 값1, 2의 비교를 통해 1이 맨앞으로 이동하게 된다. 이때 1이 스왑을 4번한것이나 마찬가지이기 때문에 병합정렬 시 해당 값들을 더하면 정답이된다.

<arr 배열>

1

3

4

5

1

6

7

8

 

2. 구현

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

public class Main1517 {

	static int N;
	static long result;
	static int[] arr;
	static int[] temp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		temp = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=1; i<=N; i++) {
			arr[i] = Integer.parseInt(st.nextToken()); 
		}
		mergeSort(1, N);
		
		System.out.println(result);
	}
	
	public static void mergeSort(int start, int end) {
		if (end-start<1) {
			return;
		}
		
		int mid = start + (end-start)/2;
		mergeSort(start, mid);
		mergeSort(mid+1, end);
		
		for (int i=start; i<=end; i++) {
			temp[i] = arr[i];
		}
		
		int k = start;
		int i = start;
		int j = mid + 1;
		while (i<=mid && j<=end) {
			if (temp[i] > temp[j]) {
				arr[k] = temp[j];
				result += j-k;
				k++;
				j++;
			} else {
				arr[k] = temp[i];
				k++;
				i++;
			}
		}
		
		while (i<=mid) {
			arr[k] = temp[i];
			k++;
			i++;
		}
		
		while (j<=end) {
			arr[k] = temp[j];
			k++;
			j++;
		}
	}
}

 

정리 : 이전에 풀었던 버블소트1만 생각하고 해당 원리를 응요해서 풀 수는 없나 계속 고민하다 결국 머지소트에 해결책이 있다는 사실을 알게 됐다. 시간복잡도에 대한 계산을 계속 미뤄왔는데 조만간 포스팅을 하면서 공부를 해야겠다.