인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

김도현님의 프로필 이미지
김도현

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

6. 바둑이 승차(이진트리 DFS)

코드 리뷰 부탁드립니다!

작성

·

202

0

이런 방식으로 풀어도 괜찮을까요?
function solution(c, arr){
                let answer=Number.MIN_SAFE_INTEGER;
                let ch = Array.from({length:arr.length+1}, ()=>0);
                function dfs(v) {
                    if(v === arr.length) {
                        let arr1 = []
                        for(let i = 0; i < arr.length; i++) {
                            if(ch[i]) arr1.push(arr[i]);
                        }
                        if(arr1.length > 0) {
                            let arr1_sum = arr1.reduce((a,b)=>a+b);
                            if(arr1_sum <= c) answer = Math.max(answer, arr1_sum);
                            else return;
                        }
                    } else {
                        ch[v] = 1;
                        dfs(v+1);
                        ch[v] = 0;
                        dfs(v+1);
                    }
                }
                dfs(0);
                return answer;
            }

            let arr=[81, 58, 42, 33, 61];
            console.log(solution(259, arr));

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

DFS를 하면서 부분집합이 하나 완성되었을 때 합을 구하는 것 보다는 영상처럼 매개변수에 매번 합하여 넘겨주는 것이 효율성이 더 좋습니다.

김도현님의 프로필 이미지
김도현

작성한 질문수

질문하기