[HackerRank/Algorithms] Sorting - Big Sorting

Problem. Sorting - Big Sorting

---

Link.

https://www.hackerrank.com/challenges/big-sorting/problem?isFullScreen=true 

Big Sorting | HackerRank

---

Description.

Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 10^6 digits. Sort the array's elements in non-decreasing, or ascending order of their integer values and return the sorted array.

 

---

Key Point. 

자바스크립트의 Number 타입은 정수를 나타낼 수 있는 값이 한정적임

(Number 타입으로 표현할 수 있는 최대값은 1.8E308이며 그 보다 큰 값은 특별한 Number 상수인 "Infinity"으로 대체됨)

 

따라서 1.8E308를 초과하는 수를 Number 타입으로 표현할 경우 문제가 발생할 수 있음!

이를 해결하기 위한 한 가지 방법은 BigInt 메소드 사용해서 수를 표현하는 방법.

 

본 문제에서도 무턱대고 아래와 같이 코드를 작성하면 test case#2와 #6를 통과하지 못함.

function bigSorting(unsorted) {
    let sorted = unsorted.sort((a, b) => {
        return a - b
    });
    return sorted;
}

 

그 이유는 배열 요소중 1.8E308를 초과하는 요소가 있었기 때문!

 

위의 코드를 아래와 같이 BigInt 메소드를 적용한 코드로 수정하였더니,

모든 test case를 통과할 수 있었음.

function bigSorting(unsorted) {
    let sorted = unsorted.sort((a, b) => {
        return Number(BigInt(a) - BigInt(b))}
    });
    return sorted;
}

 

자바스크립트에서 아주 큰 수를 다룰때 타입 사용에 주의해야겠음!!!

---

My Answer. 

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'bigSorting' function below.
 *
 * The function is expected to return a STRING_ARRAY.
 * The function accepts STRING_ARRAY unsorted as parameter.
 */

function bigSorting(unsorted) {
    let sorted = unsorted.sort((a, b) => {
        return Number(BigInt(a) - BigInt(b))}
        );
    return sorted;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    let unsorted = [];

    for (let i = 0; i < n; i++) {
        const unsortedItem = readLine();
        unsorted.push(unsortedItem);
    }

    const result = bigSorting(unsorted);

    ws.write(result.join('\n') + '\n');

    ws.end();
}

---

References. 

자바스크립트에서 아주 큰 수 다루기 (BigInt): 

https://velog.io/@baemjoon/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EC%97%90%EC%84%9C-%EC%95%84%EC%A3%BC-%ED%81%B0-%EC%88%98-%EB%8B%A4%EB%A3%A8%EA%B8%B0-BigInt-7fk5kmrh0n

자바스크립트에서 아주 큰 수 다루기 (BigInt)

 

Number (MDN): 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Number

Number - JavaScript | MDN