2021-06-05Algorithm8 minutes read (About 1132 words) 0 visits

[자바JAVA]백준 2751 수 정렬하기2 풀이

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

입출력예시

//입력
5
5
4
3
2
1

//출력
1
2
3
4
5

처음시도한 코드

시간초과로 실패
Arrays.sort()는 dual-pivot Quicksort 알고리즘사용한다. 평균 시간복잡도가 O(nlogn) 으로 좋은 알고리즘이지만 최악 시간복잡도는 O(n2) 이기때문에 퀵정렬이라고해서 다 좋은 것은 아니다.

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());

	// 배열에 숫자 넣기
	int[] arr = new int[N];
	for(int i=0; i<N; i++){
	  arr[i] = Integer.parseInt(br.readLine());
	}

	// 오름차순 정렬
	Arrays.sort(arr);

	// 출력
	for(int n : arr){
	  System.out.println(n);
	}
}

성공한 코드

memory 160156 runtime 1396

Collections.sort()는 Arrays.sort()와 달리 Timesort정렬을 사용한다. Timesort정렬는 삽입정렬과 반복합병 알고리즘 2개를 함께 사용하여 최악 시간복잡도 O(nlogn)을 보장한다.
참고로 System.out.println()만으로 출력하면 시간초과 발생하므로 꼭 StringBuilder 사용해줘야한다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
	
    // 리스트에 숫자넣기
    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);
}

풀이

메서드	알고리즘명	평균시간복잡도	최악 시간복잡도
Arrays.sort()	퀵정렬dual-pivot Quicksort	O(nlogn)	O(n2)
Collections.sort()	Timesort정렬	O(n)	O(nlogn)

아래 블로그에서 항상 도움을 많이 얻고 있다. 자바로 알고리즘 공부하는 사람에게는 바이블적인 블로그가 아닐까싶다.

일단, 최악의 경우에도 O(nlogn) 을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야 한다. 이에 대한 해결 방법은 두 가지가 있다.
첫 번째는 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 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.
시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다.
출처: https://st-lab.tistory.com/106

여담

최근 st-lab 티스토리를 운영하고 있는 블로거 ST님에게서 연락을 받았다.
제목은 포스팅 내용 변경건.
내가 잘 못 포스팅한 게 있었나? 내 포스팅이 마음에 안들어서 내려달라고 연락하신걸까? 네이버블로거들 사이에서보단 뭐 기업과 블로거의 법적대응 뭐 이런건가. 그런 영화같은 일이 소시민인 나에게…?
오만가지 생각을 하며 열어 본 이메일에는 나는 박수를 칠 수 밖에 없었다.

세상에 이렇게 멋있는 사람이 있나 싶어서.

이메일의 주 내용은 원글에 수정사항이 있는데 자칫 오해할 수 있는 내용이 있어 수정했으며 내용을 참고하신 분들에게 잘못된 내용을 전달될 수 있을까봐 해당 내용을 확인 후 반영해달라는 것이었다.
세상에 이렇게 멋진 사람이 있다니.
그의 책임감에 감탄했다.
그는 지식공유자를 넘어 신뢰감있는 전문가였다.
ST님같은 전문가가 되고 싶다.

(원문 수정내용을 반영 완료)