[백준] 2751번 - 수 정렬하기2

문제

 

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

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

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

 

풀이과정

 

1.규칙

• 입력된 값을 오름차순 정렬 합니다.

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어집니다.

2.순서

 

데이터가 많으므로 시간복잡도를 고려해야 합니다.

여러 정렬 방법이 있겠지만, 저는 시간복잡도가 best/worst : O(n log n)인 합병정렬(merge sort)로 구현하였습니다.

 

gif출처 : 위키백과

합병정렬에 대한 자세한 사항은 [위키백과 - 합병정렬] 을 참고해 주세요

 

3.코드

 

* 정렬된 데이터를 cout << endl 으로 출력했을땐 시간초과지만 cout << '\n'로 출력했을땐 정답인 이유 : endl 은 매번 output buffer를 flush 해주기에 cout << '\n'나 printf()보다 느린 경향이 있습니다 *

endl이 느린이유 : https://www.acmicpc.net/board/view/17888

각 언어별 출력속도비교 : https://www.acmicpc.net/blog/view/57