[백준 11652] 카드 with Node.js

문제 링크

www.acmicpc.net/problem/11652

11652번: 카드

풀이

const [n, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length/2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    let i = 0; let j = 0;
    const sorted = [];

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            sorted.push(left[i]);
            i++;
        }
        else {
            sorted.push(right[j]);
            j++;
        }
    }

    if (i < left.length) sorted.push(...left.slice(i));
    if (j < right.length) sorted.push(...right.slice(j));

    return sorted;
}

const sorted_arr = mergeSort(arr.map(v => BigInt(v)));
let maxCount = 0;
let curCount = 0;
let prevNumber = "";
let largest = 2**62;
sorted_arr.forEach(v => {
    if (prevNumber !== v) {
        prevNumber = v;
        curCount = 0;
    }
    curCount++;
    if ((curCount > maxCount) || (curCount === maxCount && largest > v)) {
        maxCount = curCount;
        largest = v;
    }
});
console.log(String(largest));

병합 정렬로 오름차순 정렬한 뒤, 정렬한 배열을 순회하면서 가장 많이 있는 수 중에서 최솟값을 출력하였다.

 

이 문제에서 주어지는 수의 범위는 -2⁶² ~ 2⁶²이다. 자바스크립트의 Number 원시 값은 2⁵³-1까지의 정수까지만을 안정적으로 나타낼 수 있으며, 이를 초과하는 범위의 수는 오차가 발생할 수 있다. 자바스크립트 내장 객체인 BigInt는 길이의 제약 없이 정수를 표현할 수 있도록 하는 객체이다. BigInt 타입의 값은 정수 리터럴에 n을 붙이거나, BigInt()를 호출하여 만들 수 있다. 따라서, 이 문제는 BigInt를 사용하여야 해결할 수 있다.