백준 1517번: 버블 소트 [분할정복][재귀] - Java

www.acmicpc.net/problem/1517

1517번: 버블 소트

 

이중for문을 통해 시간복잡도 O(n^2)인 기본적인 버블소트 알고리즘으로는 시간 초과!

package algorithm.boj;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Fun1517 {

	public static int[] map;
	public static int cnt = 0, N;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		map = new int[N];

		for (int i = 0; i < N; i++) {
			map[i] = sc.nextInt();
		}

		// solve
		solve(N);

		System.out.println(cnt);
		
		for(int i : map) {
			System.out.print(i+" ");
		}
		System.out.println();
	}

	public static void solve(int idx) {

		if (idx == 1)
			return;
		else {
			
			for (int i = 0; i < idx; i++) {
				for (int j = i+1; j < idx; j++) {
					
					if(map[i]>map[j]) {
						cnt++;
						int temp = map[i];
						map[i] = map[j];
						map[j] = temp;
					}
				}
			}
			
			solve(idx - 1);

		}

	}

}

 

향상된 버블정렬인 1개의 for문으로 O(n) 했는데도 시간 초과!

	public static void solve(int idx) {

		if (idx == 1)
			return;
		else {

			for (int i = 0; i < idx-1; i++) {

				if (map[i] > map[i+1]) {
					cnt++;
					int temp = map[i];
					map[i] = map[i+1];
					map[i+1] = temp;
				}

			}

			solve(idx - 1);

		}

	}

 

 

이건.. 머지소트(병합정렬) Merge sort를 이용해서 구현해야 하는 것이였다..

머지소트의 시간복잡도는 O(nlogn)이다. 머지하니까 깃이 생각나는군 머지머지

 

병합정렬은 배열의 길이가 1이 될때까지 다 쪼갰다가 다시 정렬하면서 붙여주는 작업이다.

merge sort의 진행 과정 (출처 : 위키피디아  https://en.wikipedia.org/wiki/Merge_sort)

카운트 증가는 병합 과정에서 왼쪽 값이 오른쪽 값 보다 클 때 왼쪽 배열에 있는 원소의 갯수만큼 계속 더해주면 된다.

마지막에 원본에 정렬한 배열을 복사해야한다.. 왜냐면 분할된 조각들은 계속 원본 map을 바라보고 있기때문에..

그때그때 병합된 상황들을 원본도 알고 있어야한다.

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

public class Main {

	public static long[] map, tmp;
	public static long cnt = 0;
	public static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		map = new long[N];
		tmp = new long[N];
		for (int i = 0; i < N; i++) {
			map[i] = Long.parseLong(st.nextToken());
		}

		// solve
		solve(0, N - 1);

		System.out.println(cnt);

//		for (int i : map) {
//			System.out.print(i + " ");
//		}
//		System.out.println();
	}

	public static void solve(int start, int end) {

		//0. 배열의 크기가 1인지 조건 확인
		if (start < end) {
			// 1. 분할을 하기위하여 절반 나누기 (분할된 오른쪽 부분의 idx 계산때문에 end/2가아닌 start+end/2)
			int mid = (start + end) / 2;

			solve(start, mid); // 2. 왼쪽 분할부분을 더 분할하기
			solve(mid + 1, end); // 3. 오른쪽 분할 부분을 더 분할하기

			// 4. 가장 작은 단위의 분할 부분부터 다시 병합하기
			int i = start;
			int j = mid + 1;
			int k = start;
			

			// i,j를 idx삼아 병합 .. 단, 분할된 배열의 길이를 벗어나지 않도록!.. cnt는 map[i]이 더 작을때 일어난다.
			while (i <= mid && j <= end) {
				// 대소 비교
				if (map[i] <= map[j]) {
					tmp[k++] = map[i++];
				} else {
					tmp[k++] = map[j++];
					cnt+= mid-i+1;
				}

			}   

			// 만약 왼/오 분할된 부분 중 작은 수가 한쪽에 몰려있어서 i,j인덱스가 끝점까지 간 경우는 따로따로 확인한다.
			while (i <= mid) {
				tmp[k++] = map[i++];
			}
			while (j <= end) {
				tmp[k++] = map[j++];  
			}


			for (int l = start; l <= end; l++) {
				map[l] = tmp[l];
			}
			
		}
	}

}