[백준 2750] 정렬 4단계. 수 정렬하기2

✨ 문제 ✨

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

= 입력 =

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

= 출력 =

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

= 예제 입력 1 =

5
5
2
3
4
1

= 예제 출력 1 =

1
2
3
4
5

✨ 정답 ✨

⛳1st try ⛳

const { json } = require("express/lib/response");
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().split("\n");
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let N = parseInt(input[0].split(' ')[0])
let notSortedArray = [];
for (let i = 1; i <= N; i++) {
    notSortedArray.push(parseInt(input[i].split(' ')[0]))
}

const merge=(left, right)=>{
    let sortedArray=[];
    while (left.length!==0&&right.length!==0){
        left[0]<=right[0] ? sortedArray.push(left.shift()):sortedArray.push(right.shift())
    }
    return [...sortedArray, ...left, ...right]
}

const sort=(array)=>{
    if (array.length===1) return array;
    let middleIndex=Math.floor(array.length/2);
    let left=array.slice(0, middleIndex);
    let right=array.slice(middleIndex,);
    return merge(sort(left), sort(right))

}

let result=sort(notSortedArray)

result.map((el)=>console.log(el))

시간 초과가 나왔다.
이유를 검색해 본 후 다시 시도하였다.

⛳ 2nd try ⛳

const { json } = require("express/lib/response");
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().split("\n");
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let N = parseInt(input[0].split(' ')[0])
let notSortedArray = [];
for (let i = 1; i <= N; i++) {
    notSortedArray.push(parseInt(input[i].split(' ')[0]))
}

const merge=(left, right)=>{
    let sortedArray=[];
    while (left.length!==0&&right.length!==0){
        left[0]<=right[0] ? sortedArray.push(left.shift()):sortedArray.push(right.shift())
    }
    return [...sortedArray, ...left, ...right]
}

const sort=(array)=>{
    if (array.length===1) return array;
    let middleIndex=Math.floor(array.length/2);
    let left=array.slice(0, middleIndex);
    let right=array.slice(middleIndex,);
    return merge(sort(left), sort(right))
}

console.log(sort(notSortedArray).join("\n"));

찾아 보니까 병합 정렬로는 안 된다고 한다.
그렇다면 이전에 구현해 보았던 퀵 소트를 사용해 보아야겠다.

⛳ 3rd try ⛳

const { json } = require("express/lib/response");
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(Number);
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number)


let notSortedArray = input.slice(1,)



const quickSort = (array) => {
    if (array.length <= 1) return array;

    // let pivot = parseInt(array[0]);
    let left = [];
    let right = [];
    let leftSorted = [];
    let rightSorted = [];

    for (let i = 1; i < array.length; i++) {
        if (parseInt(array[i]) < parseInt(array[0])) {
            left.push(parseInt(array[i]))
        } else {
            right.push(parseInt(array[i]))
        }
    }

        leftSorted = quickSort(left);

        rightSorted = quickSort(right);
    return [...leftSorted, parseInt(array[0]), ...rightSorted]
}
console.log(quickSort(notSortedArray).join("\n"));

퀵소트도 안 된다. 메모리 초과가 뜬다.
변수를 최소한으로 줄여 보았으나 node.js는 퀵소트에 필요한 최소한의 배열 개수도 감당을 못 하는 것 같다. 어쩔 수 없이 내장 함수를 사용하기로 하였다.

⛳ 4th try ⛳

const { json } = require("express/lib/response");
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(Number);
// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(Number)

console.log(input.slice(1,).sort((a,b)=>a-b).join('\n'))

드디어 되었다. 근데 이게 맞는지는 모르겠다.

💡💡 기억해야 할 점 💡💡

console.log()는 매우 느리다.
이를 반복적으로 돌리는 것은 매우 좋지 않다.

출처 : https://www.acmicpc.net/board/view/47265