1422 숫자의 신 (자바스크립트)

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

=====

문제 풀이

최대 수를 출력하기 위해선 우선 가장 큰 수를 n-k 만큼 세워둔다.

세워두는 것은 stack 이라는 배열에 넣을 것이다. 이제 큰 수를 하나씩 끄집어내서 stack에 각 자리에 넣어보며 더 큰 수를 만들면 된다.

각 자리에 넣어보면서 큰 수를 만드는 과정은 이진 탐색으로 진행하였다.

특정 중간 인덱스를 기준으로 그 값과 넣어야 할 값으로 만들 수 있는 두 값을 비교하여 pivot을 뒤에 놨을 떄 더 큰 값이 됐다면 넣어야 할 값을 앞으로 더 보내도 되는 것이니 e=mid-1 , pivot을 앞으로 놨을 때 더 작다면 뒤로 보내도 되는거니 s-mid+1을 두어 최종적으로 s가 있을 곳이 value를 넣을 자리이다.

큰 수대로 하나씩 끄집어내는 것을 힙큐로 동작시켰는데 그냥 입력 배열을 오름차순으로 한 뒤 하나씩 pop 하면 됐겠다 싶다.

정답 코드

class Heapq {
    hq;
    constructor() {
        this.hq = [undefined];
    }
    isExist() {
        return this.hq.length > 1;
    }
    swap(src, des) {
        [this.hq[src], this.hq[des]] = [this.hq[des], this.hq[src]];
    }
    isSmall(src, target) {
        if (this.hq[src][0] < this.hq[target][0]) {
            return true;
        }
        return false;
    }
    size() {
        return this.hq.length;
    }
    push(arr) {
        this.hq.push(arr);
        let cur = this.size() - 1;
        while (cur > 1) {
            const parent = Math.floor(cur / 2);
            if (this.isSmall(cur, parent)) {
                this.swap(cur, parent);
                cur = parent;
            } else {
                break;
            }
        }
    }
    pop() {
        if (!this.isExist()) return undefined;
        const root = this.hq[1];
        const tale = this.hq.pop();
        if (!this.isExist()) return root;
        this.hq[1] = tale;
        let cur = 1;
        while (cur * 2 < this.size()) {
            let smallest = cur * 2;
            if (smallest + 1 < this.size()) {
                if (this.isSmall(smallest + 1, smallest)) {
                    smallest += 1;
                }
            }
            if (this.isSmall(smallest, cur)) {
                this.swap(smallest, cur);
                cur = smallest;
            } else {
                break;
            }
        }
        return root;
    }
    firstNumberOfRoot() {
        if (!this.isExist()) return false;
        return String(this.hq[1][0])[1];
    }
}

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const nums = input.slice(1).map(Number);

const hq = new Heapq();

for (const v of nums) {
    hq.push([-1 * v]);
}

let diff = m - n;
const stack = [];

while (diff > 0) {
    const [v] = hq.pop();
    const num = v * -1;
    stack.push(num);
    hq.push([v]);
    diff--;
}

const binary = (value) => {
    let s = 0;
    let e = stack.length - 1;
    const strValue = String(value);
    const a = strValue[0];

    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        const strNumOfMid = String(stack[mid]);

        const aa = Number(strValue + strNumOfMid);
        const bb = Number(strNumOfMid + strValue);
        if (aa > bb) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return s;
};

while (hq.isExist()) {
    const v = hq.pop()[0] * -1;
    const idx = binary(v);
    stack.splice(idx, 0, v);
}

console.log(stack.join(''));