[백준알고리즘-JAVA]10989번 풀이(수 정렬하기3) - 초보도 이해하는 풀이

안녕하세요

인포 돈입니다.

백준 알고리즘 10989번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 10989 (수 정렬하기 3)

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

시간제한

• ava 8: 3 초
• Java 8 (OpenJDK): 3 초
• Java 11: 3 초

메모리 제한

• Java 8: 512 MB
• Java 8 (OpenJDK): 512 MB
• Java 11: 512 MB

입력 예시

10
5
2
3
1
4
2
3
5
1
7

출력 예시

1
1
2
2
3
3
4
5
5
7

성공 코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	int[] n = new int[num];
	   	 	StringBuilder sb = new StringBuilder();
	   	 	
	   	 	for(int i = 0 ; i < n.length ; i++) {
	   	 		n[i] = Integer.parseInt(br.readLine());
	   	 	}
	   	 	
	   	 	Arrays.sort(n);
	   	 	
	   	 	for(int i = 0 ; i < num ; i ++)
	   	 		sb.append(n[i]).append("\n");
	   	 	
	   	 	System.out.println(sb);
	   	 	}
		}

수 정렬하기 알고리즘의 마지막 단계로 이번에는 메모리의 사용량을 고려해보아야 하는 문제이다. 물론 이전에 설명했던 정렬의 종류, 시간 복잡도에 관한 자세한 설명은 해당 알고리즘에서는 건너뛰겠습니다.

 

해당 관련 정보가 필요하시다면  이전 글을 참고해 주세요~

[백준알고리즘-JAVA]2751번 풀이(수 정렬하기2) - 초보도 이해하는 풀이

 

해당 알고리즘에서 앞서 말했듯이 메모리를 어느 정도 잡아먹는지가 가장 중요한 관점입니다. 그러면서 해당 제한시간인 3초도 만족해야 하지요

 

그러면 STEP을 밟기 전에 간단히 정렬의 시간 복잡도와 메모리에 대한 표를 보여드릴게요

정렬 정류	최고 시간 만족도	평균	최저 시간 만족도	메모리
Bubble sort	O(n)	O(n^2)	O(n^2)	O(1)
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)
Heap sort	O(n)	O(nlogn)	O(nlogn)	O(1)
Merge sort	O(nlogn)	O(nlogn)	O(nlogn)	O(n)
Quick sort	O(nlogn)	O(nlogn)	O(n^2)	O(logn)

 

앞선 수 정렬하기 2 알고리즘에서는 Collection 정렬과 Array 정렬에 대해서 설명을 했다. 해당 알고리즘에서는 메모리에 제한이 없으며 시간제한만 존재하기 때문에 무조건적으로 빠르게 정렬할 수 있는 Collection 정렬을 사용하였다.

 

그러나 해당 문제에서는 해당 제한시간과 메모리 용량을 만족해야 한다. 정확히 우리가 3초의 시간을 측정하여 얼마나 걸리는지 측정할 수는 없지만, 이전에 사용했단 Collection 정렬로 정렬하게 된다면, 메모리 초과의 에러가 나오게 될 것입니다.

 

이에 따라서 저희는 메모리의 사용량이 적은 방법을 찾아야 합니다.

 

Collections 정렬의 경우 insertion, Merge 정렬을 병합하여 사용합니다. O(1) ~ O(n)의 메모리를 사 지게 되죠. 만약 최악의 경우 O(n)의 메모리를 차지하여 해당 알고리즘에서 제한된 메모리를 넘기게 됩니다.

 

그렇다면 Array 정렬은 듀얼 피봇 퀵 정렬을 사용하여 정렬합니다. 해당 정렬방법은 일반적인 퀵 정렬과는 다르게 피봇을 2개를 두고 정렬을 하기 때문에 퀵 정렬보다 최저 시간 만족도가 작아지게 됩니다. 

 

이에 따라서 Collection보다 작은 메모리를 사용하면서 시간제한은 만족하는 정렬 방법이 바로 Array.sort방법입니다. 이외에다 배열을 이용하거나, 또 다른 정렬방법으로 알고리즘을 푸신 분도 많이 있다는 것을 항상 생각해 주셔야 합니다 ~

---

알고리즘 흐름도

입력받기 -> 입력값 정수를 변환하기 -> 변환한 정수 Array.sort로 정렬하기 -> 출력하기

---

STEP1 입력값 정수로 변환하기

for(int i = 0 ; i < n.length ; i++) {
	   	 		n[i] = Integer.parseInt(br.readLine());
	   	 	}

뭐... 해당 코드는 사실 크게 해설해 드릴 부분이 없습니다. 여기서 n은 사용자게에 첫 번째로 입력받은 값의 크기로 만든 int 배열입니다.

 

그 크기만큼 반복하면서 입력을 계속 받아서 배열에 넣어주는 방식이죠

---

STEP2 변환한 정수 Array.sort로 정렬하기

Arrays.sort(n);

정수로 바꾼 값을 해당 정렬 메서드를 사용해주면 알아서 정렬!

---

STEP3 출력하기

for(int i = 0 ; i < num ; i ++)
	   	 		sb.append(n[i]).append("\n");
	   	 	
	   	 	System.out.println(sb);

보다 시간을 단축하기 위해 println보다는 StringBuilder를 사용해서 출력을 했습니다~

---

사실 해당 STEP들은 굉장히 간단한 코드입니다. 그러나 앞서 정렬에 대한 깊은 지식이 없다면, 쉬운 길을 두고 어렵게 해결할 수밖에 없었던 알고리즘이라고 생각합니다~