[백준 온라인 저지] 2751. 수 정렬하기 2

1. 입력

- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

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

 

2. 출력

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

 

3. 코드

1) 첫 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] nums = new int[Integer.valueOf(br.readLine())];
        for(int i=0 ; i<nums.length ; i++)
            nums[i] = Integer.valueOf(br.readLine());
        Arrays.sort(nums);
        for(int i=0; i<nums.length; i++)
            bw.write(nums[i]+"\n");
        bw.flush();
        bw.close();
    }
}

2) 병합 정렬로 다시 풀어본 코드(2023/05/23)

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] nums = new int[Integer.valueOf(br.readLine())];
        for(int i=0 ; i<nums.length ; i++)
            nums[i] = Integer.valueOf(br.readLine());
        mergesort(nums, 0, nums.length-1);
        for(int i=0; i<nums.length; i++)
            bw.write(nums[i]+"\n");
        bw.flush();
        bw.close();
    }
    
    static void mergesort(int[] arr, int start, int end) {
    	if(start<end) {
    		int mid = (start+end)/2;
    		mergesort(arr, start, mid);
    		mergesort(arr, mid+1, end);
    		merge(arr, start, mid, end);
    	}
    }
    
    static void merge(int[] arr, int start, int mid, int end) {
    	int[] sorted = new int[end-start+1];
    	int i = start, j = mid+1, k = 0;
    	while(i<=mid && j<=end) {
    		if(arr[i]<=arr[j])
    			sorted[k] = arr[i++];
    		else
    			sorted[k] = arr[j++];
    		k++;
    	}
    	if(i>mid)
    		for(int l=j ; l<=end ; l++)
    			sorted[k++] = arr[l];
    	else
    		for(int l=i ; l<=mid ; l++)
    			sorted[k++] = arr[l];
    	for(i=start, j=0; i<=end ; i++, j++)
    		arr[i] = sorted[j];
    }
}

- 메모리를 더 많이 잡아먹긴 했지만, 시간이 많이 줄어들었다.