[백준] 23336번 : A Sorting Problem(JAVA)

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

23336번: A Sorting Problem

풀이

기본적인 2중 for문 버블정렬을 할 시 시간초과가 나온다.

분할정복으로 부분을 나눠서 체크해주면 된다.

 

#출처 : https://cceeun.tistory.com/125

 

소스코드

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

public class Main {
	static long[] num, temp;
	static long answer = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		
		num = new long[n];
		temp = new long[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			num[i] = Long.parseLong(st.nextToken());
		}
		
		solve(0, n - 1);
		
		System.out.print(answer);
	}
	
	public static void solve(int start, int end) {
		if(start < end) {
			int mid = (start + end) / 2;
			
			solve(start, mid);
			solve(mid + 1, end);//분할
			
			int i = start;
			int j = mid + 1;
			int k = start;
			
			while(i <= mid && j <= end) {
				if(num[i] <= num[j]) {
					temp[k++] = num[i++];
				}
				else {
					temp[k++] = num[j++];
					answer += mid - i + 1;
				}
			}//대소 비교
			
			while(i <= mid) {
				temp[k++] = num[i++];
			}
			while(j <= end) {
				temp[k++] = num[j++];
			}//만약 작은수가 한쪽에 밀려있으면 i,j 인덱스를 끝까지해서 체크함
			
			for(int l = start; l <= end; l++) {
				num[l] = temp[l];
			}
		}
	}
}