[BOJ] 1422 숫자의 신 with JavaScript

JavaScript를 이용한 BOJ 1422 숫자의 신을 풀이한 글입니다.

문제

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

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

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

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

입력

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

출력

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

풀이

문제의 조건에 주어진 수를 모두 활용해야 하고, 중복을 허용하다는 조건이 있습니다.
만약 주어진 수를 모두 활용할 필요가 없고 중복을 허용 한다면,
만들 수 있는 수중 가장 큰 값은 입력으로 주어진 수중 가장 큰 값을 연속해서 나열한 값이 될 것입니다.
하지만 모두 최소 1번은 사용해야 하므로 주어진 입력의 최대 값을 가장 많이 사용하는 방식이 해당 문제의 답이 될 것입니다.
이제 max값 n - k + 1개와 나머지 값이 각각 1개씩 존재하는 배열을 만들고 해당 값을 적절히 배치시켜 답이 도출해야 합니다.
이는 문자열의 비교 특성을 활용해 해결할 수 있습니다.
수 '123' + '321'을 더하면 '123321'이 되고 '321' + '123'을 더하면 '321123'이 됩니다. 이 두개를 비교했을 때 '321' + '123'이
더 크므로 '321'을 앞으로 '123'을 뒤로 오도록 위치를 지정할 수 있습니다. 이를 활용해 배열을 적절히 정렬하고,
해당 값을 이어주면 가장 큰 수를 만들수 있게 됩니다.

구현

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [k, n] = input[0].split(' ').map(Number);
const num = input.slice(1);
const max = Math.max(...num);

// 두 문자열을 연결 했을 때 값이 더 큰게 앞에 오도록 정렬하는 함수
function compare(a, b) {
  if (a + b > b + a) {
    return -1;
  } else {
    return 1;
  }
}

for (let i = 0; i < n - k; i++) {
  num.push(max.toString());
}

let ans = '';
// compare함수를 통해 배열의 정렬한 후 차례대로 값을 연결해 수를 만들어 준다.
num.sort(compare).forEach((n) => {
  ans += n;
});

console.log(ans);

https://github.com/jgjung9/algorithm-test-practice