[JS] 코딩 테스트 문제 : 합이 같은 부분집합 [DFS]

문제 : 합이 같은 부분집합(DFS)

문제 설명

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000
이하입니다.

▣ 출력설명

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

▣ 입력예제 1

6
1 3 5 6 7 10

▣ 출력예제 1

YES

내코드

function solution(arr) {
  let answer = "NO";

  // 집합의 원소로 구성된 배열 arr 의 인덱스를 값을 의미할 파라미터 i
  // 두 가지 부분집합을 나누기 위한 배열 파라미터 lSet, rSet (콘솔에서 확인 및 이해를 돕기 위한 용도)
  // 두 가지 부분집합의 합을 저장할 문자열 파라미터 leftN, rightN
  // 위 파라미터를 가지는 재귀함수 DFS 선언
  function DFS(i = 0, leftN = 0, rightN = 0, lSet = [], rSet = []) {
    // 보완가능 부분: 이미 answer 값이 "YES" 라면 이후 불필요한 작업하지 않고 return 처리
    // if (answer === "YES") return;
    // 모든 원소를 부분집합으로 분리완료 된 경우
    if (i === arr.length) {
      // 확인을 위한 콘솔 출력
      console.log(
        `left 집합: ${lSet}  합: ${leftN} | right 집합: ${rSet}  합: ${rightN}`
      );
      // 두 부분집합의 합이 같다면 정답 문자열에 YES 로 변경
      if (leftN === rightN) {
        console.log("정답 확인");
        answer = "YES";
      }
    }
    // 좌측 부분집합에 i 번째 원소를 집어넣고 재귀함수 호출
    else {
      DFS(i + 1, leftN + arr[i], rightN, [...lSet, arr[i]], rSet);

      // 재귀함수를 통해 좌측 부분 집합(lSet)에 가능한 모든 부분집합의 경우의 수와 우측 부분집합(rSet)에 가능한 모든 부분집합의 경우의 수는 같고
      // 두 부분 집합의 합만 구하면 되기 떄문에 좌측 부분집합(lSet)과 우측 부분집합(rSet)을 구분할 필요가 없으므로 우측 부분집합 경우의 수를 제외
      if (i > 0)
        // 우측 부분집합에 i 번째 원소를 집어넣고 재귀함수 호출
        DFS(i + 1, leftN, rightN + arr[i], lSet, [...rSet, arr[i]]);
    }
  }

  DFS();
  return answer;
}

풀이

1. 인덱스를 값을 의미할 매개변수 i 부분집합을 나누기 위한 배열 매개변수 lSet, rSet 두 가지 부분집합의 합을 저장할 문자열 매개변수 leftN, rightN 를 가지는 재귀함수 DFS 선언
2. 좌측 부분집합에 i 번째 원소를 집어넣고 재귀함수 호출하고 우측 부분집합에 i 번째 원소를 집어넣고 재귀함수 호출하면서 가능한 두 부분집합의 경우의 수에 맞게 재귀함수 처리
3. 편의상 두개의 부분집합으로 구분했지만 좌측 부분집합(lSet)과 우측 부분집합(rSet)을 구분할 필요가 없으므로 코드상 우측 부분집합 경우의 수를 제외
4. 모든 원소를 부분집합으로 분리완료 된 경우에서 두 부분집합의 합이 같다면 정답 문자열에 YES 로 변경
5. 재귀함수가 모두 처리된 후 정답 문자열을 반환

보완할 수 있는 부분

// 기존코드
if (i === arr.length) {
  // 확인을 위한 콘솔 출력
  console.log(`left 집합: ${lSet}  합: ${leftN} | right 집합: ${rSet}  합: ${rightN}`);
  // 두 부분집합의 합이 같다면 정답 문자열에 YES 로 변경
  if (leftN === rightN) {
    console.log("정답 확인");
    answer = "YES";
  }
}
// 보완코드
// 이미 두 부분집합의 원소의 합이 서로 같은 경우 즉 answer 값이 "YES" 라면 이후 불필요한 작업하지 않고 return 처리
if (answer === "YES") return;
if (i === arr.length) {
  // 확인을 위한 콘솔 출력
  console.log(`left 집합: ${lSet}  합: ${leftN} | right 집합: ${rSet}  합: ${rightN}`);
  // 두 부분집합의 합이 같다면 정답 문자열에 YES 로 변경
  if (leftN === rightN) {
    console.log("정답 확인");
    answer = "YES";
  }
}

이미 두 부분집합의 원소의 합이 서로 같은 경우가 나왔다면 추가적으로 부분집합을 구하지 않아도 되므로 answer 값이 "YES" 라면 이후 불필요한 작업하지 않고 return 처리

다른 해결 방법

  // 정답지 방법
  function solution(arr) {
  let answer = "NO",
    flag = 0; // 정답을 구했는지 여부 0 : 찾지못한 상태  1 : 이미 찾은 상태
  // 집합의 원소로 구성된 배열의 원소들 총합
  let total = arr.reduce((a, b) => a + b, 0);
  let n = arr.length;

  // 배열의 인덱스를 의미할 파라미터 L, 한쪽 부분집합의 총합을 의미할 파라미터 sum
  // 위 파라미터를 가지는 재귀함수 DFS 를 선언
  function DFS(L, sum) {
    // 이미 두 부분집합의 원소의 합이 서로 같은 경우 즉 flas 값이 1 이라면 이후 불필요한 작업하지 않고 return 처리
    if (flag) return;

    // 모든 원소를 부분집합으로 분리완료 된 경우
    if (L === n) {
      // 배열의 총합(total)에서 한쪽 부분집합의 합(sum) 을 뺀 값이 sum 과 같다면 두 부분 집합의 값이 같다는 것을 의미
      if (total - sum === sum) {
        answer = "YES";
        flag = 1;
      }
    } else {
      // 한쪽 부분집합에 L 번째 원소를 집어넣고 재귀함수 호출
      DFS(L + 1, sum + arr[L]);
      // 한쪽 부분집합에 L 번째 원소를 집어넣지 않고 재귀함수 호출
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

풀이

1. 집합의 원소로 구성된 배열의 원소들을 순회하며 배열원소들의 총합을 total 변수에 초기화
2. 배열의 인덱스를 의미할 파라미터 L, 한쪽 부분집합의 총합을 의미할 파라미터 sum 을 가지는 재귀함수 DFS 를 선언
3. 한쪽 부분집합에 L 번째 원소를 집어넣고 재귀함수 호출하고 한쪽 부분집합에 L 번째 원소를 집어넣지 않고 재귀함수 호출해 가능한 부분집합들의 합의 경우의 수를 확인
4. 모든 원소를 부분집합으로 분리완료 된 경우에 배열의 총합(total)에서 한쪽 부분집합의 합(sum) 을 뺀 값이 sum 과 같다면 두 부분 집합의 값이 같다는 것을 의미하므로 이 경우에 정답 문자열에 YES 로 변경
5. 이미 두 부분집합의 원소의 합이 서로 같은 경우 즉 flas 값이 1 이라면 이후 불필요한 작업하지 않고 return 처리

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64100