N으로 표현

programmers.co.kr/learn/courses/30/lessons/42895?language=javascript

코딩테스트 연습 - N으로 표현

문제풀이

 

1. N의 최소 사용횟수가 8번보다 크면 -1을 반환하도록 제한되어있으므로 N을 1번 사용하는 것에서부터 8번사용하는 것까지를 순차적으로 숫자를 만들어보고, 1번부터 8번 집합에 각각 저장합니다. 그리고 number가 만들어졌는지 확인하면 됩니다.
2. N이 5일때 5는 N을 1번 사용한 것이고, 55는 2번, 555는 3번, 5555는 4번, 55555555는 8번 사용한 것 입니다. 이를 각각의 집합에 미리 추가해줍니다.
3. 1번 집합에 들어갈 수 있는 숫자는 5 하나 밖에 없습니다. 2번 집합에는 55외에 들어갈 수 있는 숫자가 있습니다. N + N, N-N, N*N, N/N. 즉, 1번 집합의 구성요소로 사측연산을 한 것입니다.
4. 3번 집합의 구성은 555와 ( 1번집합의 구성요소 +-*/ 2번집합의 구성요소),  ( 2번집합의 구성요소 +-*/ 1번집합의 구성요소) 입니다.
5. 4번 집합의 구성은 5555와 ( 1번집합의 구성요소 +-*/ 3번집합의 구성요소),  ( 2번집합의 구성요소 +-*/ 2번집합의 구성요소),  ( 3번집합의 구성요소 +-*/ 1번집합의 구성요소) 입니다.
6. 만들어진 숫자 중 타겟인 number이 발견되면 바로 집합 번호를 반환하면 됩니다.
7. 순회가 모두 끝난 후에도 number를 발견하지 못했다면, 최소횟수가 8이상인 것이므로 -1를 반환합니다.

function solution(N, number) {
    const set = new Array(9).fill().map(() => new Set());
    for (let i = 1; i <= 8; i++) {
        set[i].add(Number(N.toString().repeat(i)));
        for (let j = 1; j < i; j++) {
            for (const arg1 of set[j]) {
                for (const arg2 of set[i - j]) {
                    set[i].add(arg1 + arg2);
                    set[i].add(arg1 - arg2);
                    set[i].add(arg1 * arg2);
                    set[i].add(arg1 / arg2);
                }
            }
        }
        if (set[i].has(number)) return i;
    }
    return -1;
}