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

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

---

• 문제

 

 

 

수 정렬하기에 이은 두 번째 문제다. 차이점이라면 데이터도 이전 문제에 비해 1000배 많아졌고, 수의 범위도 1000배 넓다.

 

 

※ 주의할 점

1. Java기준 Arrays.sort 로 쓰면 시간초과가 날 가능성이 높다.   (2021.01.11 Java → Java8 명칭이 변경됨)

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이 문제를 풀기 전에 참고했으면 하는 글 두 개를 넣겠다. 문제를 푸는데 있어 매우 도움이 될 것이다.

 

st-lab.tistory.com/105

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

 

 

st-lab.tistory.com/104

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

 

 

 

 

 

이 문제는 대부분 Arrays.sort 로 풀면 시간초과가 난다.

(위는 Java8 기준이다. 참고로 자바의 버전마다 조금씩 다르기 때문에 다른 버전으로 제출하면 통과될 수 있다.)

 

Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 했다. 물론 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘인 것은 맞다. 그러나 최악의 경우 시간복잡도는 O(n²) 이라는 점을 기억해야한다.

 

이 문제는 단순하게 Arrays.sort() 를 쓰지 못하게 일부러 O(n²) 이 걸리도록 저격한 데이터가 있다. 그래서 아마 Arrays.sort 방법을 써서 제출하다가 틀린 사람이 한 둘이 아니다. (필자의 경우도 저격데이터가 있는지 모르고 제출했다가 틀렸었다... 방심했다..)

 

 

 

 

그렇다면 어떻게 해결해야될까? 

 

일단, 최악의 경우에도 O(nlogn) 을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야 한다. 이에 대한 해결 방법은 두 가지가 있다.

 

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

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

시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다. 대신에 Collections.sort()를 사용하고자 한다면 가장 쉬운 방법으로는 일반적인 primitive 배열이 아닌 List 계열(ArrayList, LinkedList 등..)의 자료구조를 사용하여 정렬해야한다.

 

자세한 내용은 아래를 참고하면 좋을 것 같다.

https://en.wikipedia.org/wiki/Timsort

Timsort - Wikipedia

 

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html#sort(java.util.Comparator)

List (Java SE 11 & JDK 11 )

 

 

물론 직접 구현해서 쓰는 방법도 있다.

Tim Sort의 구현은 필자가 포스팅 한 Tim Sort 구현 포스팅을 참고하시기를 바란다.

 

 

 

두 번째는 필자가 위 링크에서 보여주었던 Counting sort (카운팅 정렬)을 응용하여 쓰는 방법이다. 이 방법은 이전 문제에서도 보여주었으니 따로 설명은 않겠다.

 

 

[추가 내용]

만약 비교 정렬을 직접 구현하여 풀고자 하면 쉽게 풀리진 않을 것이다. 이미 자바에서 제공하는 정렬 알고리즘은 최적화까지 모두 고려하여 작성되어있다. 만약 직접 정렬을 구현 할 것이라면 적절한 최적화를 해야 할 것이다. (특히나 퀵정렬로 구현하고자 하는 경우는 일반적인 구현방식으로는 더욱이 힘들 것이다.)

 

필자의 블로그의 메뉴를 보면 알고리즘 메뉴에서 정렬 알고리즘도 다루고 있는 것을 볼 수 있다.

필자도 정렬 알고리즘을 포스팅하면서 한 번 필자가 구현한 것들을 테스트 해봤는데 통과되는 정렬 알고리즘이 몇 개가 존재한다. (아직 Tim Sort는 포스팅하기 전이라 이후 포스팅한다면 테스트해보고 여기에 기록을 남기도록 하겠다.)

 

1. Shell Sort (셸 정렬)

2. Heap Sort (힙 정렬)

3. Merge Sort (합병/병합 정렬)

4. Tim Sort (팀 정렬)

 

위 3가지 알고리즘은 약 700 ~900ms (BufferedReader, StringBuilder 사용) 가량의 시간이 걸리는 것으로 나온다.

 

만약 좀 더 최적화되고 다양한 타입에서도 정렬할 수 있는 구현을 보고싶다면 아래 필자의 깃허브 repo를 참고해주시길 바란다.

https://github.com/kdgyun/Sorting_Algorithm

kdgyun/Sorting_Algorithm

 

 

 

 

 

 

 

---

• 3가지 방법을 이용하여 풀이한다.

 

 

먼저 Collections 에서 제공하는 sort 를 사용한 방법에 더해 Scanner 와 BufferedReader 을 사용한 방법을 보여줄 것이다. 다음으로는 Counting Sort 를 응용하여 써 볼 것이고, Counting sort 방법은 BufferedReader 로만 보여주고자 한다. 

 

그리고 가장 중요한점!

테스트해본 결과 Scanner 로 입력받아 sort 를 쓸 경우 출력은 BufferedWriter 을 쓰던가, StringBuilder를 써서 한 번에 출력해주어야 한다. 아니면 시간 초과가 나기 때문이다. 그러므로 필자는 여러분들이 가장 접근하기 쉬운 StringBuilder 로 보여주겠다.

 

---

• 풀이

- 방법 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);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

ArrayList 에 모든 원소를 입력받아 저장하고 Collections 패키지에 있는 sort() 를 사용하여 정렬을 한다.

 

 

 

 

 

---

- 방법 2 : BufferedReader + Collections.sort

 

 

Scanner 대신 BufferedReader 로 입력받아 사용하는 방법이다.

 

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 {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		// list 계열 중 하나를 쓰면 된다.
		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

 

 

필자가 이전 포스팅에서도 썼던 방법이다. (상단 링크 참고)

수가 중복되지도 않기 때문에 boolean[] 배열에 입력 받은 값을 index로 쓰면 되는데, 아무래도 직접 비교 정렬이 아니므로 시간복잡도는 O(n) 으로 매우 빠른 방법이다.

 

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

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 100000 으로 생각
		*/
		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.print(sb);
	}
}

 

 

 

수의 범위가 -1,000,000 ~ 1,000,000 이므로 0의 기준을 인덱스 1,000,000 으로 잡는다. 이 점만 주의하면 나머지는 이해하기 쉬울 것이다.

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 20102310  -  방법 3 : BufferedReader + Counting sort

채점 번호 : 20102307  -  방법 2 : BufferedReader + Collections.sort

채점 번호 : 20102304  -  방법 1 : Scanner + Collections.sort

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 압도적으로 빠른 걸 볼 수 있다.. (데이터가 많을 수록 그 차이는 더욱 크다)

 

또한 Counting Sort 를 사용한 방식으로 하니 메모리도, 시간도 엄청나게 줄어든다는 점을 볼 수 있다.

---

• 정리

 

 

오늘은 약간의 낚시성 문제인 것 같았다.

 

퀵 정렬이라고 항상 quick 인 것은 아니라는 점을 간과해서 그런지 틀린 분들도 엄청나게 많다. 특히 quick sort 의 경우 '거의 정렬 된 형태'의 수열의 경우가 최악의 경우로 시간복잡도가 O(n²) 에 가까워진다. 그렇기 때문에 각 정렬메소드에 대한 이해를 하고 있을 필요가 있다.