백준 2751 (정렬)

문제

---

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

---

정렬할 수 있는 방식은 많은데 시간적으로 시간복잡도가 적은 알고리즘을 선택해서 풀어보고자 풀이를 했다.

합병정렬을 사용하여서 코드를 작성 하였는데.. 찾아보니 다른 C++ 같은 언어에서는 사용이 가능 하였지만

기본적으로 자바가 시간을 많이 소비되는(?) 언어라 그런가 합병정렬도 오류가 났다. 

 

<합병정렬 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int n;
	static int[] list;
	
	public static void main(String[] args) throws NumberFormatException, IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		list = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			list[i] = Integer.parseInt(br.readLine());
		}
		
		mergeSort(0, n-1);
		
		for(int i = 0 ; i < n ; i++) {
			System.out.println(list[i]);
		}
	}
	
	static void mergeSort(int s, int e){
		
		if(s >= e)
			return;
		
		int m = (s+e)/2;
		
		mergeSort(s, m);
		mergeSort(m+1, e);
		
		merge(s, e, m);
	}
	
	static void merge(int s, int e, int m) {
		
		int i = 0;
		int j= s, k=m+1;
		int[] copy = new int[(e - s) + 1];
		
		while(i <= (e-s)) {
			if(j <= m && k <= e) {
				if(list[j] < list[k]) {
					copy[i] = list[j];
					j++;
				}
				else {
					copy[i] = list[k];
					k++;
				}
				i++;
			}
			else if( j <= m ) {
				copy[i] = list[j];
				i++;
				j++;
			}
			else if( k <= m) {
				copy[i] = list[k];
				k++;
				i++;
			}
		}
		
		i = 0;
		for(j = s, i= 0 ; j <= e ; j++, i++) {
			list[j] = copy[i];
		}
		
		return;
	}
}

 

 

그래서 자바를 이용해서 풀 수 있는 방법을 찾던중 List 의 Collections.sort 의 메소드를 이용하면 풀 수 있다고 하여 풀어 보았다. 

여기서 sort 메소드는 TimSort 알고리즘을 사용한다.

 

TimSort 알고리즘은 합병알고리즘과 선택알고리즘을 둘다 사용하는 개면이라고 한다. 또, 데이터가 램덤하게 흩어진 형태 보다는, 대략 정렬된 상태로 있다는 것에 기반하여 디자인된 알고리즘 이다.

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {	
	
	public static void main(String[] args) throws IOException{
		
		int n;
		List<Integer> list;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		list = new ArrayList<Integer>();
		
		for(int i = 0 ; i < n ; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		StringBuilder sb = new StringBuilder();
		
		for(int value : list) {
			sb.append(value).append('\n');
		}
		
		System.out.println(sb);
	}
}