[JavaSrcipt] Baekjoon - 2751 : 수 정렬하기 2

✅ 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다.

예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

 

문제

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

입력

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

출력

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

 

예제입력	예제출력
5 5 4 3 2 1	1 2 3 4 5

 

⭕ 풀이

const input=require('fs').readFileSync('/dev/stdin').toString().trim();
let arr=input.split('\n').map(x=>Number(x));
let t=arr.shift();

arr.sort(function(a,b){
    return a-b;
})
console.log(arr.join('\n'));

 

사이트에서 언급했듯이 시간복잡도가 O(n log n)인 정렬알고리즘으로 해결가능하다.

그중 대표적인게 Heapsort, Mergesort 등이 있다.

 

이외에도 이전시간에 포스팅했던 

거품정렬, 삽입정렬, 선택정렬 같은경우들은 시간복잡도가 O(n²) 이며

Quicksort, Shellsort, Smoothsort 등 여러 정렬알고리즘들이 있다.

 

이번시간에는 보통 재귀함수를 사용해서 정렬하는방식의

병합정렬을 사용해서 풀이해보려고했으나

아직 코드풀이가 제대로 이해되지않아서 우선 차선책이었던

언어에 내장된 정렬함수 sort를 사용했다.

 

Algorithms	best	average	worst
Bubble	O(n)	O(n²)	O(n²)
Insertion	O(n)	O(n²)	O(n²)
Selection	O(n²)	O(n²)	O(n²)
Merge	O(n log n)	O(n log n)	O(n log n)
Heap	O(n log n)	O(n log n)	O(n log n)
Quick	O(n log n)	O(n log n)	O(n²)
Shell	O(n)	O(n log n²)	O(n log n²)
Smooth	O(n)	O(n log n²)	O(n log n²)

 

 

 

-출처

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