[백준] 알고리즘 2751번 : 수 정렬하기 2 With 자바

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

내가 생각했던 것은 아 정렬이니까 정렬중에서도 여러가지가 있지만 병합정렬을 써보자 해서 병합정렬을 썼다.

import java.util.*;

public class NewApp {

	private static int[] sorted;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int number=scan.nextInt();
		
		int []array=new int[number];
		int i=0;
		int num;
		while(i<number) {
			num=scan.nextInt();
			array[i]=num;
			i++;
		}
		
		sort(array,number);
		
		i=0;
		while(i<number) {
			System.out.println(array[i]);
			i++;
		}
	}
	
    

    public static void sort(int []a,int right) {
        sorted=new int[right];
        divideandconquer(a,0,right-1);
        sorted=null;
    }

    private static void divideandconquer(int []a, int left,int right) {
        int mid;
        if(left<right) {
            mid=(left+right)/2;

            divideandconquer(a,left,mid);
            divideandconquer(a,mid+1,right);

            merge(a,left,mid,right);
        }
    }

    private static void merge(int []a, int left,int mid,int right) {
        int l=left;
        int r=mid+1;
        int idx=left; //새로운배열에 넣기 위함

        while(l<=mid && r<=right) {
            if(a[l]<=a[r]) {
                sorted[idx]=a[l++];
            }else {
                sorted[idx]=a[r++];
            }
            idx++;
        }

        if(l>mid) {
            while(r<=right) {
                sorted[idx++]=a[r++];
            }
        }else {
            while(l<=mid) {
                sorted[idx++]=a[l++];
            }
        }

        for(int i=left; i<=right; i++) {
            a[i]=sorted[i];
        }


    }

}

하지만 채점 결과 시간초과라는 것이 나왔다 이때 합병정렬이 시간복잡도가 NlogN으로 이것이 시간초과라면 다른데에 문제가 있나 보다 하고선 검색을 한 결과 System.out.println이라는 것 때문이었다. 해결방법으로는 StringBuilder를 썼다.

StringBuilder vs System.out.println 와의 차이점

System.out.println은 출력을 하기 위해 사용하는데 내부적으로 synchronized block으로 씌여져 있다.

public void println(String x) { 
		synchronized (this) { 
        	print(x); 
            newLine(); 
        } 
}

synchronized는 동기화(공유 데이터가 작업 중인 스레드가 마칠 때까지 다른 스레드에서 접근하지 못하도록 하기 위한 것)로 작업중인 스레드가 마칠 때까지 다른 스레드들이 대기시간이 발생한다는 것이다. System.out.println 또한 동기화가 적용되어 있는 것인데 이것으로 인해 오버헤드가 발생해 성능 저하를 초래하게 된다. 그래서 프로젝트나 알고리즘문제에서 출력할 데이터들을 모아두고 한번에 System.out.println으로 출력한다고 한다.

그래서 StringBuilder 클래스는 String과 동일하지만 문자열을 보다 쉽게 조작할 수 있는 클래스로 이것을 사용한다.

import java.util.*;

public class Main {

	private static int[] sorted;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		StringBuilder sb = new StringBuilder(); //추가된 코드
		int number=scan.nextInt();
		
		int []array=new int[number];
		int i=0;
		int num;
		while(i<number) {
			num=scan.nextInt();
			array[i]=num;
			i++;
		}
		
		sort(array,number);
        
		//추가및 변경된 코드
		for(int value : array) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
	}
	
    

    public static void sort(int []a,int right) {
        sorted=new int[right];
        divideandconquer(a,0,right-1);
        sorted=null;
    }

    private static void divideandconquer(int []a, int left,int right) {
        int mid;
        if(left<right) {
            mid=(left+right)/2;

            divideandconquer(a,left,mid);
            divideandconquer(a,mid+1,right);

            merge(a,left,mid,right);
        }
    }

    private static void merge(int []a, int left,int mid,int right) {
        int l=left;
        int r=mid+1;
        int idx=left; //새로운배열에 넣기 위함

        while(l<=mid && r<=right) {
            if(a[l]<=a[r]) {
                sorted[idx]=a[l++];
            }else {
                sorted[idx]=a[r++];
            }
            idx++;
        }

        if(l>mid) {
            while(r<=right) {
                sorted[idx++]=a[r++];
            }
        }else {
            while(l<=mid) {
                sorted[idx++]=a[l++];
            }
        }

        for(int i=left; i<=right; i++) {
            a[i]=sorted[i];
        }


    }

}

위와 같이 하면 해결하게 된다.

 

그리고 합병정렬을 직접구현하는 것이 아닌 Collections 에서 제공하는 sort 를 사용하는 방법이 있다고 한다.

Scanner + Collections.sort 하는 방법, BufferedReader + Collections.sort 하는 방법등등이 있다 

시간이 된다면 이것을 구현 한것을 밑에 추가하겠다.