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

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

박제영님의 프로필 이미지
박제영

작성한 질문수

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

5. 합이 같은 부분집합(이진트리 DFS)

이렇게 될 경우 서로소임에도 판별하지 않는 경우가 생기던데..

작성

·

217

0

지금의 코드의 경우 flag 제거하면

[1,3,5,7] = [6,10] / [1,5,10] = [3,6,7]

인 부분집합만 판별을 하던데요 (이 두가지 케이스만 걸림

([6,10] = [1,3,5,7] / [1,3,5,7] = [6,10]이런식으로 순서 바뀐것까지 포함해서 4가지인데 결국 2개나 마찬가지)

[1,6] = [7]

이런 케이스는 판별이 안되는데..

그렇다면 지금 코드가 완벽하지 않을수도 잇다는 생각이

드는데요

지금 코드로도 어떤 케이스든 다 판별이 가능한게 맞을까요?

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡfunction solution(arr) {

    let answer = [];

    let check = Array.from({length:arr.length},()=>0);

 

    function DFS(idx) {

        if(idx === arr.length) {

            let temp = [];

            let temp2 = [];

            for(let i=0; i<check.length; ++i) {

                if(check[i] === 1) temp.push(arr[i]);

                else  temp2.push(arr[i]);

            }

            let sum1 = temp.reduce((acc,v)=>{return acc + v;},0)

            let sum2 = temp2.reduce((acc,v)=>{return acc + v;},0)

            if(sum1 === sum2)  

                answer.push('YES');

        }else {

            check[idx] = 1;

            DFS(idx+1);

            check[idx] = 0;

            DFS(idx+1);

        }

    }

    DFS(0);

    //* 부분집합 64개 만들기

    //* 서로소인 집합을 추리기 -

    //* 서로소인 집합의 합을 비교해서 같은 대상이 잇나 검색

}

 

let arr=[1, 3, 5, 6, 7, 10];

console.log(solution(arr));

 

답변 1

0

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

안녕하세요^^

문제에 보면 

둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.

 

두 부분집합을 합하면 원래 입력으로 주어진 집합이 되어야 합니다.

 

박제영님의 프로필 이미지
박제영
질문자

아 그렇군요 감사합니다

박제영님의 프로필 이미지
박제영

작성한 질문수

질문하기