[프로그래머스] N으로 표현 - 자바스크립트

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

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

크으.. 드디어 dp첫 문제를 풀었다 + 마지막으로 식을 정리하는데, 모던 자바스크립트 deep dive에서 공부한 블록문에 대해서 이해를 하고 식을 정리하니 소름이 쫙!!! 뭐  후자같은 경우에는, 별로 문제 풀이에는 연관이 없으니 여기서는 설명하지 않겠습니다.

dp에 대해 설명을 하자면 다이나믹 프로그래밍 한글로, 동적 계획법의 약자로, 지금 같은 숫자를 끊어서 계산하는 경우에는, 계산한 값들을 5+5, 5/5, 5-5, 5*5와 같이 5를 사용한 숫자와 함께 그 결과를 계속적으로 사용을 하기 때문에 이에 대한 리스트를 만들고, 메모리에서 사용하는 문제를 말한다.

문제 풀이 플로우는 다음과 같다.

1. 이 문제에서는 8개 이상이 되는 숫자를 사용하지 않으니 0~8개까지의 5가 사용된 (예시 '', '5', ... '555555'...) 숫자들을, 세트에 넣어서 리스트에 넣는다. 세트에 넣는 이유는 굳이 중복을 만들어서 여러번 계산할 필요가 없기 때문이다

2. 몇번 사용했는지에 대한 loop문을 사용하고 그안에 i보다 적게 사용된 루프문으로 다시 감싼다

for(let i=0;i<9;i++){
	for(let j=0;j<i;j++{
    }
}

여기서 9까지만 사용한 이유는 숫자는 8개가 넘어가는 경우에는 return -1을 해줘야하기 때문이다

3. 2번의 루프문 안에, j가 사용됬을때의 set와, i-j가 사용됬을 때의 set를 호출한다

for(let x of list[j]){
	for(let j of list[i-j]{
    }
}

i-j를 구하는 방법은, 지금은 i를 구하는 것이 중요하기에 x와 y의 N숫자 사용 갯수가 i가 되게 만들기 위해서이다.

4. 3에서 만든 x와 y를 이용하여 4칙연산을 만들고, 이 값들이 만약에, number(주어진 숫자)와 같다면 return i를 하고 그렇지 않다면 list[i]의 set에 넣는다.

5. 4의 경우가 없다면 return -1을 한다

6. 이때, 1번에서 만든 숫자들의 경우는 체크가 안되기 때문에, 2번 앞부분에, 

for(let i=0;i<list.length;i++)if(list[i].has(number)) return i

을 넣어 줌으로써, number가 set안에 들어가있으면 return i를 하게 넣는다.

 

전체코드는 다음과 같다

function solution(N, number) {
    const list = Array.from({length:9}).map((me, index) => new Set ([Number(String(N).repeat(index))]))
    for(let i=0;i<list.length;i++)if(list[i].has(number)) return i
    for (let i =1;i<9;i++){
        for(let j=1;j<i;j++){
            for(let x of list[j]){
                for(let y of list[i-j]){
                    const calc = [a,b,c,d] = [x+y, x-y, x*y, x/y]
                    for(component of calc)list[i].add(component)
                    if(a===number)return i
                    if(b===number)return i
                    if(c===number)return i
                    if(d===number)return i
                }
            }
        }
    }
    return -1
}