문제

BOJ 11931: 수 정렬하기 4 https://www.acmicpc.net/problem/11931

풀이

조건

• N개의 수가 주어졌을 때, 이를 내림차순으로 정렬한다.

풀이 순서

• 원본 배열은 arr, 복사해놓을 배열은 temp로 한다.

코드

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

public class Main {  
	
	static int N;
	static int[] arr;
	static int[] temp;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		temp = new int[arr.length];
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		mergeSort(arr, 0, N-1);
		
		for(int i=0; i<arr.length; i++) {
			sb.append(arr[i]).append("\n");
		}
		
		System.out.println(sb);
		
	}
	
	static void mergeSort(int[] arr, int s, int e) {
		// 크기가 1보다 크면
		if(s < e) {
			int m = (s + e) / 2;
			
			mergeSort(arr, s, m);
			mergeSort(arr, m+1, e);
			merge(arr, s, m, e);
		}
		
		
	}
	
	static void merge(int[] arr, int s, int m, int e) {
		int i = s; // 앞 덩어리 포인터
		int j = m + 1; // 뒤 덩어리 포인터
		int k = s; // temp 배열 포인터
		
		// 큰 순서대로 배열에 삽입
		while(i <= m && j <= e) {
			if(arr[i] >= arr[j]) {
				temp[k] = arr[i];
				i++;
			} else {
				temp[k] = arr[j];
				j++;
			}
			k++;
		}
		
		// 남은거 넣기
		if(i > m) {
			for(int t=j; t<=e; t++) {
				temp[k] = arr[t];
				k++;
			}
		} else {
			for(int t=i; t<=m; t++) {
				temp[k] = arr[t];
				k++;
			}
		}
		
		// 정렬된 결과를 원래 배열에 넣기
		for(int t=s; t<=e; t++) {
			arr[t] = temp[t];
		}
		
	}
		
}  

정리

• 정렬 중 병합 정렬(Merge Sort)를 사용했다.