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

문제

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

시행착오 1

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있다길래, 병합정렬로 풀려고 했는데 시간초과가 생겼다.

아래 코드와 비슷한거 같은데 왜 시간이 더 걸리는 걸까ㅠ

import java.util.Scanner;
public class Main {
	private static void mergeSort(int[] arr) {
		int[] tmp = new int[arr.length];
		mergeSort(arr, tmp, 0, arr.length-1);
	}
	private static void mergeSort(int[] arr, int[] tmp, int start, int end) {
		if(start < end) {
			int mid = (start + end)/2;
			mergeSort(arr, tmp, start, mid);
			mergeSort(arr, tmp, mid+1, end);
			merge(arr, tmp, start, mid, end);
		}
	}
	private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
		for(int i=start; i<=end; i++) {
			tmp[i] = arr[i];
		}
		int part1 = start;
		int part2 = mid+1;
		int index = start;
		
		while(part1<=mid && part2<=end) {
			if(tmp[part1]<=tmp[part2]) {
				arr[index]=tmp[part1];
				part1++;
			}else {
				arr[index]=tmp[part2];
				part2++;
			}
			index++;
		}
		for(int i=0; i<mid-part1; i++) {
			arr[index+i]=tmp[part1+i];
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = in.nextInt();
		}
		mergeSort(arr);
		for(int data : arr) {
			System.out.println(data);
		}
	}
}

 

2년전 코드 (성공)

왜 이건 되고 위 코드는 안될까ㅠ...

import java.util.Scanner;

public class Main {
	public static void merge(int[] a1, int[] a2, int[] a3){
		int n1=0, n2=0, n3=0;
		
		while(n1<a1.length){
			if(n2<a2.length){
				if(a1[n1]<a2[n2]){
					a3[n3]=a1[n1];
					n1++;
				}else{
					a3[n3]=a2[n2];
					n2++;
				}
				n3++;
			}else{
				while(n1<a1.length){
					a3[n3]=a1[n1];
					n1++;
					n3++;
				}
			}
		}
		while (n2<a2.length){
			a3[n3]=a2[n2];
			n2++;
			n3++;
		}
		
		
	}
	public static void merge_sort(int[] arr, int n){
		if(n==1) return;
		
		int[] arr_temp1 = new int[n/2];
		int[] arr_temp2 = new int[n-n/2];
		
		for(int i=0; i<n/2 ; i++){
			arr_temp1[i]=arr[i];
		}
		for(int i=0 ; i<n-n/2 ; i++ ){
			arr_temp2[i]=arr[n/2+i];
		}
		
		merge_sort(arr_temp1,n/2);
		merge_sort(arr_temp2,n-n/2);
		
		merge(arr_temp1, arr_temp2, arr);
		
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		
		// 숫자들이 들어갈 배열 nums
		int[] nums = new int[N];
		for(int i=0 ; i<nums.length ; i++){
			nums[i]=in.nextInt();
		}
        
		merge_sort(nums,N);        
		for(int i=0; i<nums.length; i++){
			System.out.println(nums[i]);
		}
	}

}

 

시행착오 2

혹시 하고 기대했던

Arrays.sort(); 장렬하게 시간초과^^...

 

https://st-lab.tistory.com/106

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]

 

위 글을 참고했다.

Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용했다고 한다.

물론 평균 시간복잡도는 O(nlogn)이지만 최악의 경우의 시간복잡도는 O(n^2)이다.

 

---

 

어떻게 해야 할까?

최악의 경우에도 O(nlogn)을 보장하거나 O(n)에 가까운 정렬 알고리즘을 사용해야 한다.

1) Collections.sort()

- Collections.sort()는 Timsort이다. Timsort의 경우 반복 합병 및 삽입정렬 알고리즘을 사용하는데, 이렇게 두가지가 섞인 정렬 알고리즘을 Hybrid stable sorting  algoritm이라고 한다.

   - 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn)을 보장하고 (근데 왜 안돼.....헝)

   - 삽입정렬(Insert Sort)의 경우 최선의 경우는 O(n), 최악의 경우는 O(n^2)이다.

   - 즉, 합병정렬의 최악 + 삽입정렬의 최선 을 합친 알고리즘이 Timsort라는 것이다.

- 시간 복잡도 : O(n) ~ O(nlogn)

2) Counting Sort (카운팅 정렬, 계수 정렬)

카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 엄청난 성능을 보이는 알고리즘이다.

보통 빠르다는 정렬 알고리즘으로는 대표적으로 퀵 정렬, 힙 정렬, 합병 정렬 등이 있는데, 이들의 시간복잡도는 O(nlogn)인 것에 비해 상당히 빠른 속도인 것을 볼 수 있다.

기본적으로 정렬이라 하면 데이터끼리 직접 비교하는 경우가 많아, O(nlogn)보다 작아질 수 없는 한계가 있다.

- 시간 복잡도 : O(n)

- 정렬 방법 : https://st-lab.tistory.com/104?category=856997

카운팅 정렬 (Counting Sort / 계수 정렬) _ Java [자바]

 

※ 중요한 점!

Scanner로 입력받아 sort를 사용할 경우, 출력은 BufferedWriter를 쓰던가, StringBuilder를 써서 한번에 출력해줘야 한다.

(아니면 시간초과 발생)

 

 

여기서 풀이 1, 풀이 2가 문제의 의도였지 않나 싶다..

풀이 1 

Scanner + Collections.sort

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
	public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        int N = in.nextInt();
        
        //list 계열 중 하나
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int i=0; i<N; i++){
        	list.add(in.nextInt());
        }
        
        Collections.sort(list);
        
        for(int value : list){
        	sb.append(value).append('\n');
        }
        
        System.out.println(sb);
    }
}

 

풀이 2

BufferedReader + Collections.sort (시간 : 1452ms)

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

public class Main{
	public static void main(String[] args) throws IOException {
		//InputStreamREader는 InputStream 객체를 입력으로 가져야 한다.(System.in) - 문자로 읽기
		//BufferedReader는 InputStreamReader의 객체를 입력값으로 사용 - 통째로 읽기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int value : list) {
			sb.append(value).append("\n");
		}
		System.out.println(sb);
	}
}

 

풀이 3

BufferedReader + Counting Sort (시간 : 676ms)

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

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		/*
		 -1000000 ~ 1000000
		 기준점 0 = index 1000000 으로 가정
		 */
		//수가 중복되지 않아 boolean
		boolean[] arr = new boolean[2000001];
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			arr[Integer.parseInt(br.readLine())+1000000] = true;
		}
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i]) {
				sb.append(i-1000000).append('\n');
			}
		}
		System.out.println(sb);
	}
}