본문 바로가기
개발/알고리즘

[프로그래머스] N으로 표현

by 자몬다 2021. 8. 12.

주어진 N을 최대한 적게 사용하여 사칙연산(+, -, *, /)으로 목표하는 number를 만들고, 최소 몇개가 필요한지 구하는 문제이다.

 

유의할 점은 N=5인 경우 두 개를 사용하면 55로도 만들 수 있지만,

그렇다고 N=5 number=105일때 

(5 + 5) = 10

10 + "5" = 105

이렇게는 할 수 없다는 점이다.

 

이미 사칙연산된 숫자에는 N을 붙일 수 없고, 사칙연산할 원소로만 사용해야 한다.

function solution(N, number) {
    var answer = 0;
    if(N == number) return 1;
    // 5
    // 55 5+5 5-5 5/5 5*5 // [55 0 10 1 25] // 55 + 사칙연산
    // 555, [55 0 10 1 25]* 사칙연산
    
    // 주어진 배열을 N으로 사칙연산하여 리턴하는 함수
    const four = (n, arr) => {
        const result = [];
        for(let i of arr) {
            result.push(i+n, i-n, Math.ceil(i/n), i*n);
        }
        return result;
    }
    
    // 주어진 배열들로 조합을 만들어내는 함수
    const comb = (arr1, arr2) => {
        const result = [];
        for(let i of arr1) {
            result.push(...four(i, arr2));
        }
        return [...new Set(result)];
    }
    
    let repeatNum = N; // 5 55 555
    let temp = [[N]]; // 1개만 사용하는 경우는 미리 추가
    // 9회차 까지만 반복한다.
    for(let i = 2; i<9;i++) {
        const arr = [];
        repeatNum = parseInt(repeatNum + N.toString());
        // 조합할 배열에 반복숫자를 추가해준다(55)
        arr.push(repeatNum);
        // 추가된 배열로 조합을 구한다.
        for(let j = 0; j<temp.length; j++) {
            arr.push(...comb(temp[j], temp[temp.length-j-1]));            
        }

        temp.push(arr.filter((a, i) => a > 0 && arr.indexOf(a) === i));
        
        if(arr.includes(number)) return i;
    }
    // 찾지 못한 경우 -1을 리턴한다.
    return -1;
}

 

https://programmers.co.kr/learn/courses/30/lessons/42895

728x90

댓글0