소수 만들기

문제

문제: https://programmers.co.kr/learn/courses/30/lessons/12977

숫자 배열 중 3개를 선택하고, 그 합이 소수(decimal)인 경우를 구하는 문제

해결방법

1. dfs함수(재쉬)를 돌면서 3개의 합을 answer에 저장한다.
2. answer을 isDecimal함수로 filter한다.
3. answer의 개수를 출력한다.

dfs함수 코드 설명

dfs함수를 통해서 숫자 배열의 모든 경우(조합-combination)을 구해서 그 합을 구해주면 된다.
이 함수는 이전 포스팅이었던 순열,조합과 같은 로직으로 구하면 된다.

[0,1,2,3,4] 배열일 때의 예시.
1. for문에서 0을 선택했을 때 -> dfs(선택한애(0) 빼고 배열,num+1,sum+0)
2. for문에서 1을 선택 -> dfs(선택한애(0,1) 빼고 배열,num+1,sum+1)
3. for 문에서 2를선택->dfs(선택한애(0,1,2) 빼고 배열,num+1,sum+2)
4. num이 3이 됐기 때문에 sum에 있는 3을 answer에 넣는다.

위의 과정을 숫자 끝까지 반복하면 된다.

dfs함수에서 종료조건아래 else를 빼고 답안을 제출 했더니 시간초과가 몇 문제 발생했다. else문으로 시간을 단축시키는 것도 중요해 보인다.

isDecimal함수

함수는 1과 자기 자신만 나누었을 때 나누어 떨어지기 때문에 2~num-1에서 나머지가 0이 아니라면 false를 반환시켰다.

code

function solution(nums) {
    let answer = []

    const dfs = (nums,num,sum) =>{
        if(num===3) answer.push(sum)
        else{
            for(let i=0; i<nums.length; i++){
                dfs(nums.slice(i+1),num+1,sum+nums[i])
            }
        }
    }
    dfs(nums,0,0)
    answer = answer.filter(num=>isDecimal(num))
    
    return answer.length;
}

function isDecimal(num) {
    for(let i=2; i<num; i++){
        if(num%i===0) return false
    }
    return true
}

---

점프와 순간이동

문제

문제: https://programmers.co.kr/learn/courses/30/lessons/12980

• +k칸 이동 - 에너지 소모: k
• 지금까지 온거리*2 순간이동 - 에너지 소모: 0

위의 2가지 경우만 선택해 목적지까지 갈때 필요한 최소 에너지

해결방법

규칙이 있다.

2로 나누었을 때, 나머지가 1이 나오게 되면 그건 한칸씩 가줘야 되기 때문에 +1해줘야 된다.

즉, 2로 나누었을 때 나머지가 1인 것의 합이니 10진수를 2진수로 변경해 1의 총합을 구하면 된다.

code

function solution(n){
    let answer = n.toString(2)
    answer = answer.split('').map(v=>v*1)
    return answer.reduce((a,b)=>a+b)
}