Programmers_42895 N으로 표현

• TOC {:toc}

이 글은 프로그래머스의 42895번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2024.04.04

function solution(N, number) {
    const dp = Array.from(new Array(9), () => []);
    // N을 나열해서 만드는 경우를 확인 후 각 dp 초기 배열에 포함
    for (let i = 0; i < 9; i++) {
        const num = Number(`${N}`.repeat(i));
        if (num === number) return i;
        dp[i].push(num);
    }
    const operation = {
        add: (a, b) => a + b,
        sub: (a, b) => a - b,
        mul: (a, b) => a * b,
        div: (a, b) => Math.floor(Math.max(a, b) / Math.min(a, b)),
    };

    // N을 2번부터 8번 사용하는 동안
    for (let count = 2; count < 9; count++) {
        // 이전에 저장한 dp[i]와 dp[count - i]의 값들을 사칙연산해 dp[count]를 구성
        for (let i = 1; i <= count / 2; i++) {
            for (const a of dp[i]) {
                for (const b of dp[count - i]) {
                    // 위에서 정의해둔 사칙연산을 순회
                    for (const op in operation) {
                        // 두 수로 사칙연산한 결과가 number와 일치하면
                        // 현재 사용된 N의 개수인 count를 바로 반환
                        const newNum = operation[op](a, b);
                        if (newNum === number) return count;
                        if (!dp[count].includes(newNum) && newNum > 0)
                            dp[count].push(newNum);
                    }
                }
            }
        }
    }

    // N을 8번 사용해도 해당되는 수를 만들지 못하면
    // -1을 반환
    return -1;
}

아이디어 & 풀이

동적 계획법을 사용해 N을 count번 사용했을 때 만들 수 있는 수를 dp[count]에 저장해가면서 주어진 number와 일치여부를 확인한다.

우선 사칙연산 외에 N을 NNN과 같이 단순히 나열해서도 수를 만들 수도 있으며 이 수들을 연산에 포함해주어야 한다.

• dp[i]를 초기화하는 과정에서 N이 i번 반복된 해당 수들을 포함시킨다.
  • N이 i번 반복된 수는 repeat 메소드를 이용해 구성한다.
• 이 과정에서 number가 해당 수와 같을 수 있으므로 number와 일치하는지 확인하고 일치한다면 사용 횟수인 i를 바로 반환한다.
  • 이 수들은 이후 사칙연산 ‘결과’를 확인하는 과정에서는 (0과는 사칙연산을 하지 않는다) 확인할 수 없으므로 이 때 일치하는지 확인하거나 사칙연산 과정에서 각 수를 확인하는 로직을 수정해야 한다.

사칙연산 결과를 구하는 과정에서 동적 계획법은 다음과 같이 사용한다.

• N을 i번 사용한 결과값과 j번 사용한 결과값이 있을 때 이 값들을 서로 사칙연산한 결과는 N을 i + j번 사용한 결과값과 같다. 이에 따라 N을 한 번 사용한 결과부터 구하기 시작해 이전에 구한 값들끼리 사칙연산을 하면서 2, 3, 4, … 번 사용했을 때 만들 수 있는 수를 구할 수 있다.
• 예를 들어 dp[2]는 dp[1]의 값들을 상호 사칙연산한 결과로 구성할 수 있다.
• dp[4]는 dp[1]의 값들과 dp[3]의 값들을 사칙연산해서 구성할 수도 있지만 dp[2]의 값들을 상호 사칙연산해서 만들 수도 있으므로 두 경우를 모두 포함해야 한다.

이를 위해 다음과 같이 반복문을 구성한다.

• 우선 N을 8번 초과로 쓰면 -1을 반환하므로 사용한 N의 개수인 count을 2부터 8까지 순회한다.
  • 한 개 사용한 경우는 사칙연산의 결과값이 아니므로 2부터 시작한다.
• 현재 count 이전의 dp[i]의 조합을 순회한다.
  • 조합은 dp[i]와 dp[count - i]로 이루어지며 i가 중간 값을 넘어가면 조합이 반복되므로 count / 2까지만 순회한다.
• 각 조합의 수에 대해 operation으로 정의한 사칙연산을 순회한다.

반복문 내에서 다음의 로직을 수행한다.

• 사칙연산의 결과가 number와 같은지 비교하고 같으면 현재 count를 바로 반환한다.
• 같지 않으면 현재 dp[count]에 해당 값을 추가한다.
  • 이 떄 중복을 피하기 위해 현재 dp[count]에 해당값이 includes 되어있는지 확인한다.
  • 음수는 포함되지 않으므로 0보다 큰 값인지도 확인한다.

반복문이 수행되는 동안 number와 일치하는 수를 찾지 못하면 number는 N 8개로는 만들 수 없는 수이므로 -1을 반환한다.

디버그

• 사칙연산이 아니라 N을 연속으로 나열해서 만든 수를 dp[i]의 초기값에는 포함시켰지만 이 경우 아래 반복문에서 해당 수가 number와 일치하는지 검사하지 않게된다.
  • 그러므로 처음 dp[i]의 초기값에 해당 수들을 집어넣을 때 해당 수가 number와 일치하는지 검사한 뒤 일치하면 바로 N이 반복되는 횟수인 i를 반환하도록 했다.
• dp[[i]와 dp[j]를 이용해 dp[i + j]를 구성할 때 시간 단축을 위해 반복을 i <= count ** 0.5까지만 하도록 했는데 경계에 있는 일부 케이스가 포함이 안되는 것 같다.
  • i <= count / 2로 조건을 수정해서 해결했다.
  • 생각해보니 애초에 루트값이 아니라 2로 나눈 값 까지 구해야 모든 케이스를 커버할 수 있다.

피드백

중복 제거를 위해 includes를 이용해 검사하는 대신 Set을 사용해 add 하면 속도가 훨씬 빨라진다.

참고 답안

function solution(N, number) {
    const dp = new Array(9).fill(0).map((el) => new Set());

    for (let i = 1; i < 9; i++) {
        dp[i].add("1".repeat(i) * N);
        for (let j = 1; j < i; j++) {
            for (const a of dp[j]) {
                for (const b of dp[i - j]) {
                    dp[i].add(a + b);
                    dp[i].add(a - b);
                    dp[i].add(a * b);
                    dp[i].add(Math.floor(a / b));
                }
            }
        }
        if (dp[i].has(number)) return i;
    }
    return -1;
}

• 중복 제거를 위해 배열대신 Set을 사용했다.
• 조건과 반복의 구분을 최소화해 위의 풀이에 비해 훨씬 간호하게 작성했다. Set으로 수정한 풀이와 비교했을 때 시간은 비교적 오래 걸리는 편이다.