수열을 2등분했을 때 곱한 값의 최댓값 찾기(JS)

문제

S = [1, 2, 3, 4, 5, 6, 7]이 주어지고 한번씩만 써서 만들 수 있는 2개의 수(a, b)가 있을 때

a, b 곱의 최댓값을 구하는 문제입니다.

풀이

완전탐색으로 접근하면 괜찮을까 고민을 해보며 부분집합으로 문제를 해결하려고 했습니다.

이러면 답이 나오긴 하지만, (123, 4567) (4567, 123) 값과 같이 불필요한 중복 값이 존재하게 됩니다.

 

따라서 방문처리를 통해, 만들어지는 두 수 중에서 하나의 수(a)의 길이가 한 번만 완성되도록 구현했습니다.

코드

let arr = [1, 2, 3, 4, 5, 6, 7];
let N = arr.length;
let v = [false, false, false, false, false];
let v2 = [false, false, false, false, false];
let ans = 0;

function subset(cur, cnt) {
  if (cur == N) {
    // 한 번만 방문하게 만듦 && 0이나 N의 길이는 하나의 수만 만들어지므로 pass
    if (v2[cnt] || cnt == N || cnt == 0) return;
    v2[cnt] = true;

    let res1 = "";
    let res2 = "";
    for (let i = 0; i < N; i++) {
      if (v[i]) res1 += arr[i];
      else res2 += arr[i];
    }

    res1 = res1
      .split("")
      .sort((a, b) => b - a)
      .join("");

    res2 = res2
      .split("")
      .sort((a, b) => b - a)
      .join("");

    ans = Math.max(ans, res2 * res1);
    return;
  }

  v[cur] = true;
  subset(cur + 1, cnt + 1);

  v[cur] = false;
  subset(cur + 1, cnt);
}

subset(0, 0);
console.log(ans);