[JAVA] BOJ(백준) - 수 정렬하기 2 - 2751

문제내용

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

2751번: 수 정렬하기 2

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

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

---

문제풀이

문제 내용은 매우간단하다. 주어진 수를 오름차순으로 정렬하기.

근데 자바를 이용해서 이문제를 푸는데는 여러가지 방법이 있는데 정렬에 대한 이부분을 짚고 넘어가면 좋을 듯하다.

 

우선 입렵값의 개수가 1000000이기 때문에 O(n^2)으로 풀면 최악의 경우 무조건 시간초과가 난다. 시간제한은 2초인데 n^2이면... 1,000,000,000,000 번 연산을 해야되기 때문에...( 대충 1억번 연산이 1초임. )

그래서 이문제를 풀려면 시간복잡도는 최악의경우 O(N) or O(NlogN)이 나와야한다.

 

여기서 우리가 대부분 잘 사용하고 있는 메소드인 Arrays.sort() 와 Collections.sort의 차이점을 보자.

 

- Arrays.sort()

이 메소드로 정렬한다면 시간초과가 나게된다. Arrays.sort()는 퀵정렬을 기반으로 정렬이 되기 때문에 평균적으로

O(NlogN)이라는 준수한 효율을 보이지만 최악은 O(N^2) 가 나오게 된다.

그리고 해당 문제에선 O(N^2)에 걸리는 데이터가 있기 때문에 무조건 시간초과가 난다.

 

- Collections.sort()

이를 이용해 풀면 통과될수 있다. Collections.sort()는 팀정렬(합병정렬 + 삽입정렬)을 기반으로 하기 때문에 언제나

O(NlogN)의 시간 복잡도를 갖게 된다.

 

- 합병정렬

필자가 개인적으로 합병정렬 알고리즘을 이용해 풀어봤는데 틀렸다. 합병정렬도 마찬가지로 언제나 O(NlogN)이라는 시간복잡도를 갖는걸로 알고 있는데, 이부분은 왜틀린건지 팀정렬과 비교가 필요해 보인다.

합병정렬(시간초과)

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

public class Main {
	static int n;
	static int[] temp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		sort(arr);
		
		for(int a:arr) {
			System.out.println(a);
		}
		
	}
	
	public static void sort(int[] arr) {
		temp = new int[arr.length];
		sort(arr,0,arr.length-1);
		temp = null;
	}
	
	public static void sort(int[] arr, int left, int right) {
		if(left==right) return;
		
		int mid = (left+right)/2;
		
		sort(arr,0,mid);
		sort(arr,mid+1,right);
		
		merge(arr,left,mid,right);
	}
	
	public static void merge(int[] arr, int left, int mid, int right) {
		int l = left;
		int r = mid+1;
		int idx = left;
		
		while(l<=mid && r<=right) {
			if(arr[l]<=arr[r]) {
				temp[idx++] = arr[l++];
			}else {
				temp[idx++] = arr[r++];
			}
		}
		
		if(l>mid) {
			while(r<=right) {
				temp[idx++] = arr[r++];
			}
		}else {
			while(l<=mid) {
				temp[idx++] = arr[l++];
			}
		}
		
		for(int i=left; i<=right; i++) {
			arr[i] = temp[i];
		}
	}
}

 

 

- Counting sort

카운팅 정렬로 풀어도 맞출수 있다. 카운팅 정렬은 말그대로 같은숫자를 세서 count라는 배열에 저장해준다. 이후 누적합으로 count배열의 요소값을 증가시키고,  요소값-1 을 통해 result배열에 넣어주면 정렬된다. 이게 말로 표현이 어려운데...

일단 머리속에 "count배열의 인덱스: 실제 수, count배열의 요소값: 실제 수의 개수"로 밖아놓고 아래 블로그에서 이해해보자.

그리고 아래 블로그에서 나와있겠지만 counting sort의 경우 정렬할 값이 많지 않다면 O(N)으로 정렬가능하기 때문에 1억개가 넘어가는것만 아니라면 써볼만한 정렬이다.

https://st-lab.tistory.com/104?category=856997 

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

 

- PriorityQueue

우선순위큐를 사용해도 맞출수 있다. 우선순위큐는 힙 정렬을 기반으로 정렬이되고 합병정렬과 마찬가지로 O(NlogN)이라는 시간복잡도를 갖고 있기 때문에 통과 가능하다. 그리고 우선순위큐도 기본적으로 오름차순 정렬이기 때문에 reverse를 따로 사용안해도 된다는점이 있다.

 

 

정렬에 대해 참고한 블로그

https://jbhs7014.tistory.com/180

[Algorithm] 여러 정렬 알고리즘의 특징과 복잡도

 

---

코드

Countiong sort

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();//정렬된값을 넣어줄 공간.
		
		int n = Integer.parseInt(br.readLine());
		
		//문제에서 수의 범위를 -1000000 ~ 1000000 으로 해줬기때문에 배열의 크기도 2배로 만듦.
		/*
		 * counting배열을 int가 아닌 boolean으로 하는 이유는
		 * 원래는 중복되는 수가 나오면 int로 해야하지만 이문제에선 중복되는 수가 없기 때문에
		 * boolean으로 해도 정렬이 가능하다. 즉, 카운트하고 누적합을 할 필요가 없다.
		 */
		boolean[] counting = new boolean[2000001]; 
		
		//couning[실제 수 + 1000000] = 실제 수의 개수 (이 문제에선 실제 수의 개수는 1개임)
		//이부분에서 실제 수가 낮은게 앞단의 인덱스로 자리잡게됨.
		for(int i=0; i<n; i++) {
			counting[Integer.parseInt(br.readLine())+1000000] = true;
		}
		
		for(int i=0; i<counting.length; i++) {
			if(counting[i]) {//i라는 수가 있다면 -> -1000000해서 원래수로 되돌려줌 -> sb에 삽입
				sb.append(i-1000000).append("\n");
			}
		}

		System.out.println(sb.toString());
		
	}
}

---

마치며

문제 자체는 쉬웠는데, 이번 문제를 통해 정렬에 대해서 다시 공부할수 있었던 기회였다. 특히 합병정렬과 카운팅정렬을 실제로 구현해보는 시간이 있어서 좋은 문제였다고 생각한다.