[BOJ / Node.js] 18511. 큰 수 구성하기

https://www.acmicpc.net/problem/18511

18511번: 큰 수 구성하기

 

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

예제 입력 1

657 3
1 5 7

예제 출력 1

577

 

Solve

• 주어진 배열을 돌며, 가능한 숫자 조합을 모두 만들고, n보다 작거나 같은 경우만 numbers에 담아 주었습니다.
• base case는 n의 길이와 조합한 숫자의 길이로 설정했으며, 조건에 맞는 숫자들 중 최대값을 출력 해주었습니다.

Problem

• base case를 n의 길이와 조합한 숫자의 길이로 설정할 경우, n이 `11111111` 이고, arr에 `1` 만 있는 경우와 같이, 배열에 담기는 숫자가 없는 case가 있었습니다. 그런 경우에는 주어진 k의 원소 중 가장 큰 값을 n-1 길이만큼 반복해주어, 예외처리를 하였습니다.
• 가장 큰 수를 구하는 것이기 때문에 굳이 numbers에 모든 경우를 저장하지 않고, max값 만 도출하는 방법이 조금 더 효율적일 것이라고 생각합니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const [n, k] = input[0].split(' ');
const arr = input[1].split(' ').map(el=>+el);

arr.sort((a,b)=>b-a);


const numbers = [];
const findNumber = (temp) => {
    if(temp.length === n.length) {
        const a = +temp.join('');
        if(a <= +n) {
            numbers.push(a)
        }
        return;
    }
    for(let i = 0 ; i < arr.length; i++) {
        findNumber([arr[i], ...temp]);
    }
}

findNumber([]);

console.log(numbers.length === 0 ? (arr[0]+"").repeat(n.length-1) : Math.max(...numbers));