2751문제 수 정렬하기2(정렬) Java

 

##포인트..##

기존에는 2750문제와 동일하길래 Arrays.sort()가 빠른줄 알고 그냥 사용했다. 그런데 실패해서 찾아보니 해당방법의 경우 최악의 경우에는 시간복잡도가 넘어간다는걸 알았고, 다른블로그에서는 해당메서드 말고

Collections.sort() 로 사용하더라

첫 번째는 Collections.sort() 를 쓰는 방법이다. Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn)  을 보장하고. 삽입정렬(Insertion sort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다. 그리고 두 정렬 모두 안정 정렬(stable sort)이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 한다.

즉, 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.

 

##기타##

Collections.sort()을 사용하려면 기존에는 int[]로 사용했는데 그 부분을 arrayList로 변경했다.

그리고 제출했더니 실패가떴..다 아래부분때문..

기존

for(int i : list) {

System.out.println(i);

}

변경

StringBuilder sb = new StringBuilder();

for(int value : list) {

sb.append(value).append('\n');

}

System.out.println(sb);

속도 차이가 많이난다.

 

라고 하는데 아래 주소로 가서 상세설명을 보는게 참 도움이 많이된다.

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

 

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

public class boj_2751 {
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		//N개
		int N = in.nextInt();
		List<Integer> list = new ArrayList<>();
		//N번 반복해서 변수를 담는다
		for(int i=0; i<N; i++) {
			list.add(in.nextInt());
		}
		//Collections.sort() 은 Timsort -> 합병 및 삽입정렬 알고리즘을 사용한다.
		Collections.sort(list);
		/*for(int i : list) {
			System.out.println(i);
		}*/
		StringBuilder sb = new StringBuilder();
		for(int value : list) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
		
		
	}

}