3687 성냥개비 (자바스크립트)

문제

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

출력

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 

=====

문제 풀이

우선 각 숫자들을 꾸릴 때 필요한 성냥개비들을 구해보면 아래와 같다.

const stickCountOfNumbers = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
    0: 6,
};

처음 문제를 풀때 min 은 Infinity, max는 -1로 만든 뒤에 큐에다가 [사용할 수 있는 성냥개비 수, 현재까지 만들어진 숫자] 를 넣은 뒤 성냥개비 수가 0 이 될 때마다 min과 max를 비교했었다.

이렇게 할 경우 예제는 맞게 나오지만 제출 시 시간 초과가 발생한다.

이것을 최적화 하는 방법을 생각해보니 숫자들을 만들 때 필요한 성냥개비 수별로 묶을 수 있었다. 

6개가 있다면 만들 수 있는 최소의 수는 0, 최대 수는 9 인 것처럼 말이다.

이것을 통해 max를 바로 구할 수 있는데 주어진 n이 짝수개라면 1을 최대한 많이 붙이면 이것이 최댓값이 될 것이다. 

만약 홀수라면 1을 최대한 쓰고 3개가 남은 시점에 맨 앞에 7를 넣어주면 이것이 최댓값이 된다. 

이를 코드화 하면 

const n = +input.shift();
let min;
let max;
if (n % 2 === 0) {
    max = '1'.repeat(n / 2);
} else {
    max = '1'.repeat(Math.floor(n / 2) - 1);
    max = '7' + max;
}

이제 최솟값을 구해보자.

최댓값을 구할 때처럼 어떠한 규칙을 찾기는 어려워서 숫자대비 만들 수 있는 최소수가 박힌 배열을 먼저 선언한다.

// 숫자, 성냥개비 수
const minArr = [
    [8, 7],
    [0, 6],
    [2, 5],
    [4, 4],
    [7, 3],
    [1, 2],
];

이제 이것을 시간초과가 발생했던 로직을 사용하여 큐에 담은 뒤 하나씩 꺼내보며 숫자를 만들면 된다.

이때 주의할 점은 1의 자리에 0이 올 수 없으므로 맨 처음 큐 생성 후 담아줄 때 minArr에서 값을 하나씩 꺼낼건데 이것이 0이라면 6을 대신 넣어준다. 왜 6이냐면, 0을 만들 때 필요한 갯수인 6개인데 6개로 만들 수 있는 그 다음 작은 수는 6이기 때문이다. 

또한 동일 성냥개비 대비 가장 작은 수를 visited 함수에 기록하는 것으로 최적화를 시켜준다.

이것으로 인해 min은 visited[0]이 된다.

아래는 숫자중 가장 맨 앞자리를 구하는 행위.

const q = [];
const visited = Array.from({ length: n + 1 }, () => Infinity);
for (const [num, cnt] of minArr) {
    if (cnt > n) continue;
    if (num === 0) {
        q.push([n - cnt, `6`]);
        visited[n - cnt] = 6;
    } else {
        q.push([n - cnt, `${num}`]);
        visited[n - cnt] = num;
    }
}

큐에 숫자를 꺼내보면서 최솟값을 visited에 기록한다.

while (q.length) {
    const [rest, str] = q.shift();
    if (rest === 0) continue;
    for (const [num, cnt] of minArr) {
        if (cnt > rest) continue;
        const value = Number(str + String(num));
        if (visited[rest - cnt] <= value) continue;
        visited[rest - cnt] = value;
        q.push([rest - cnt, String(value)]);
    }
}
min = visited[0];

정답 코드

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

const minArr = [
    [8, 7],
    [0, 6],
    [2, 5],
    [4, 4],
    [7, 3],
    [1, 2],
];

const answer = [];
input.shift();
while (input.length) {
    const n = +input.shift();
    let min;
    let max;
    if (n % 2 === 0) {
        max = '1'.repeat(n / 2);
    } else {
        max = '1'.repeat(Math.floor(n / 2) - 1);
        max = '7' + max;
    }
const q = [];
const visited = Array.from({ length: n + 1 }, () => Infinity);
for (const [num, cnt] of minArr) {
    if (cnt > n) continue;
    if (num === 0) {
        q.push([n - cnt, `6`]);
        visited[n - cnt] = 6;
    } else {
        q.push([n - cnt, `${num}`]);
        visited[n - cnt] = num;
    }
}
while (q.length) {
    const [rest, str] = q.shift();
    if (rest === 0) continue;
    for (const [num, cnt] of minArr) {
        if (cnt > rest) continue;
        const value = Number(str + String(num));
        if (visited[rest - cnt] <= value) continue;
        visited[rest - cnt] = value;
        q.push([rest - cnt, String(value)]);
    }
}
min = visited[0];

    answer.push(`${min} ${max}`);
}
console.log(answer.join('\n'));

 

 

const q = [];
const visited = array.from ({길이 : n + 1}, () => infinity);
for (minarr의 const [num, cnt]) {
if (cnt> n) 계속;
if (num === 0) {
Q.push ([n -cnt,`6`]);
방문 [n -cnt] = 6;
} 또 다른 {
q.push ([n -cnt,`$ {num}`]);
방문 [n -cnt] = num;
}
}