[백준/2751]수 정렬하기2 - 자바

 

문제

 수 정렬하기1과 유사하지만 개수가 1,000,000개 이기 때문에 유의해야 할 것들이 있었습니다. 물론 선택,버블,삽입 과 같은 정렬로는 안되고 log의 시간 복잡도를 가지는 알고리즘으로 풀어야 하는데 퀵과 병합을 배웠기 때문에 사용해봤습니다.

 

하지만 정렬되어 있을 경우 퀵정렬은 최악의 시간 복잡도 N^2를 가지기 때문에 안나올 것입니다.

동빈나님은 어찌어찌 되었지만 저는 안되더라구요. 그래서 병합정렬로 해보았습니다.

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	//수 정렬하기 2
	
	static int[] sorted;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Main sort = new Main();
		
		int t = Integer.parseInt(bf.readLine());
		int[] arr = new int[t];
		sorted = new int[t];
		for(int i=0;i<t;i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}
		
		sort.mergeSort(arr,0,arr.length-1);
		
		for(int i=0;i<arr.length;i++) {
	    	  bw.write(String.valueOf(arr[i])+"\n"); // 출력
	     }
		
		bw.flush();
	    bw.close();
	}
	public void mergeSort(int[] arr,int x,int y) {
		
		if(x<y) {
			int mid = (x+y)/2;
			mergeSort(arr, x, mid);
			mergeSort(arr, mid+1, y);
			merge(arr,x,mid,y);
		}
	}
	public static void merge(int[] arr,int x,int mid,int y) {
		
		int i = x;
		int j = mid+1;
		int k = x;
		
		while(i<=mid && j<=y) {
			if(arr[i] < arr[j]) {
				sorted[k] = arr[i];
				i++;
			}else {
				sorted[k] = arr[j];
				j++;
			}
			k++;
		}
		
		if(i>mid) {
			for(int t=j;t<=y;t++) {
				sorted[k] = arr[t];
				k++;
			}
		}else {
			for(int t=i;t<=mid;t++) {
				sorted[k] = arr[t];
				k++;
			}
		}
		
		for(int t=x;t<=y;t++) {
			arr[t] = sorted[t];
		}	
	}
}

 

이와 같이 풀었는데 처음엔 곧죽어도 시간 초과가 떠서 너무 짜증났는데.. 역시나 기본이 젤 중요한지 입출력을 더 생각해야 했었어요. 저는 입력만 bufferedreader로 받아서 했는데 출력도 bufferedWriter를 사용해야 시간초과가 안나오더라구요. ㅜㅜ 역시 공부 부족입니다. bufferedWriter는 익숙치가 않은데 공부해야겠습니다.