[실버] 수 정렬하기2 (2751번)_JS

문제

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

 

입력

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

 

출력

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

 

속도 제일 최적 내 답안:
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n").map(Number)  ;
input.shift() ;

**let arr = new Array(1000000).fill(0) ;
let maArr = new Array(1000000).fill(0) ;**
let answer = "" ;

input.forEach(x => {
    if (x >= 0) arr[x] = 1 ;
    else maArr[x*(-1)] = 1 ;
}) ;

for (let j = maArr.length-1 ; j > 0 ; j-- ){
    if (maArr[j] == 1 ) answer += `${(-1)*j}\\n` ;   
}
for (let i = 0 ; i < arr.length ; i++ ){
    if (arr[i] == 1 ) answer += `${i}\n` ;
}

console.log(answer.trim());

**
>> 음수와 양수를 나누어서 arr를 만듦 > 속도가 줄어들음
>> 정수여서 가능한 방법

 

 

>> 아래는 실패답안: 퀵정렬

내 시간초과 답안: 퀵정렬이어도 기존에 정렬되어있으면 n*n이 될 수 있어서 그럼..
function qS(arr, a, b){ //a,b = index ;
    if (a >= b) return 
    let pri = a, left = a+1, right = b, val ;
    while (left <= right ){
        while ((left <= b)&&(arr[left] <= arr[pri])) left++
        while ((right > a)&&(arr[right] >= arr[pri])) right--
        if (left > right) {
            val = arr[right] ;
            arr[right] = arr[pri] ;
            arr[pri] = val ;
        } else {
            val = arr[right] ;
            arr[right] = arr[left] ;
            arr[left] = val ;
        }
    }
    qS(arr, a, right-1) ;  //왼쪽arr 재귀함수
    qS(arr, right+1, b) ;  //오른쪽arr 재귀함수
}

qS(input,0,input.length-1) ;
console.log(input.join("\\n"))