[알고리즘] N으로 표현

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

나의 풀이

const N = 5;
const number = 12;

function formula(N, expression, array) {
  const type = ["*", "+", "-", "/"];
  const before = expression[expression.length - 1];
  const open = expression.split("(").length;
  const close = expression.split(")").length;

  if (expression.split(N).length > 8) {
    return;
  } else if (!type.includes(before)) {
    const exp = expression.split(N);
    array.push(expression.replace(exp.pop(), ""));
  }

  if (before === N)
    for (let i = 0; i < type.length; i++) {
      formula(N, expression + type[i], array);
    }

  if (before !== ")") formula(N, expression + N, array);

  if (open === close) {
    if (before !== N && before !== ")") {
      if (expression === "5*5*5*5*(5*5") {
        console.log("????");
      }
      formula(N, expression + "(", array);
    }
  } else if (before !== "(" && !type.includes(before)) {
    formula(N, expression + ")", array);
  }
}

function solution(N, number) {
  var answer = 0;
  let value = { "+": 1, "-": 2, "*": 3, "/": 4, "(": 5, ")": 0 };
  let arr = [];

  formula(N.toString(), "5", arr);

  arr = [...new Set(arr)];

  console.log(arr.length, arr);

  for (let i = 4999; i < 5000; i++) {
    const reg = /[*\-()\/+]/g;
    const reg2 = /[^*\-()\/+]/g;
    let exp = "5+5*5+(5+5-55/5)";
    const open = exp.split("(").length;
    const close = exp.split(")").length;

    if (open !== close) {
      exp += ")";
      exp = exp.replace("()", "");
    }
    const num = exp.split(reg).filter((data) => data);
    const ex = exp.split(reg2).join("").split("");

    console.log(num, ex, exp);

    const stack = [];
    for (let j = 0; j < ex.length; j++) {
      const num1 = num[j];
      const num2 = num[j + 1];

      const next = ex[j + 1];

      if (value[ex[j]] >= ex[j + 1]) {
        let sum = 0;
        switch (ex[j]) {
          case "+":
            sum = num1 + num2;
            break;
          case "-":
            sum = num1 - num2;
            break;
          case "*":
            sum = num1 * num2;
            break;
          case "/":
            sum = parseInt(num1 / num2);
            break;
        }
      }
    }
  }

  return answer;
}

solution(N, number);

최초엔 재귀함수를 사용해서 나올 수 있는 모든 경우의 수를 식으로 표현해서 계산을 하려고 작업했다. 

식으로 나타내는것은 가능했는데, 일반적인 계산을 하고자하니, 중위식 계산으론 작업이 어렵다는 것을 느꼇다. 

 

const N = 5;
const number = 12;

// 연속된 괄호
function changeIntoPost(expression) {
  const stack = [];
  let postfixString = [];
  let temp = "";

  for (let i = 0; i < expression.length; i++) {
    let ch = expression[i];

    if (ch === "(") {
      stack.push(ch);
    } else if (ch === ")") {
      let oper = stack.pop();
      postfixString.push(temp);
      while (stack.length !== 0 && oper !== "(") {
        postfixString.push(oper);
        oper = stack.pop();
      }
      temp = "";
    } else if (ch === "+" || ch === "-") {
      if (stack.length === 0) {
        postfixString.push(temp);
        stack.push(ch);
        temp = "";
      } else {
        postfixString.push(temp);
        while (stack.length !== 0) {
          let oper = stack.pop();

          if (oper === "(") {
            stack.push(oper);
            break;
          }
          postfixString.push(oper);
        }

        temp = "";
        stack.push(ch);
      }
    } else if (ch === "*" || ch === "/") {
      if (stack.length === 0) {
        postfixString.push(temp);
        stack.push(ch);
        temp = "";
      } else {
        postfixString.push(temp);
        while (stack.length !== 0) {
          let oper = stack.pop();

          if (oper === "(" || oper === "+" || oper === "-") {
            stack.push(oper);
            break;
          }
          postfixString.push(oper);
        }

        temp = "";
        stack.push(ch);
      }
    } else {
      temp += ch;
    }
  }

  postfixString.push(temp);

  while (stack.length !== 0) {
    let oper = stack.pop();

    if (oper === "(") {
      stack.push(oper);
      break;
    }
    postfixString.push(oper);
  }

  return postfixString.filter((data) => data);
}

function evalPostfix(expression, number, N) {
  let exp = changeIntoPost(expression);

  let stack = [];

  let num1 = 0;
  let num2 = 0;

  for (let i = 0; i < exp.length; i++) {
    ch = exp[i];
    console.log(stack);

    if (ch === "+" || ch === "-" || ch === "*" || ch === "/") {
      num2 = parseInt(stack.pop());
      num1 = parseInt(stack.pop());

      switch (ch) {
        case "+":
          stack.push(num1 + num2);
          break;
        case "-":
          stack.push(num1 - num2);
          break;
        case "*":
          stack.push(num1 * num2);
          break;
        case "/":
          stack.push(parseInt(num1 / num2));
          break;
      }
    } else {
      stack.push(ch);
    }
  }

  let test = stack.pop();

  if (number === test) {
    return expression.split(N).length;
  } else {
    return 999;
  }
}

function formula(N, expression, array) {
  const type = ["*", "+", "-", "/"];
  const before = expression[expression.length - 1];
  const open = expression.split("(").length;
  const close = expression.split(")").length;

  if (expression.split(N).length > 8) {
    return;
  } else if (!type.includes(before)) {
    const exp = expression.split(N);
    const exp2 = expression.split(N);

    array.push(expression.replace(exp.pop(), ""));
  }

  if (before === N || before === ")")
    for (let i = 0; i < type.length; i++) {
      formula(N, expression + type[i], array);
    }

  if (before !== ")") formula(N, expression + N, array);

  if (open === close) {
    if (before !== N && before !== ")") {
      formula(N, expression + "(", array);
    }
  } else if (before !== "(" && !type.includes(before)) {
    formula(N, expression + ")", array);
  }
}

function solution(N, number) {
  var answer = 999;

  let arr = [];

  let strN = N.toString();

  formula(strN, "", arr);

  arr = [...new Set(arr)];

  console.log(arr);

  for (let i = 0; i < arr.length; i++) {
    let exp = arr[i];

    const open = exp.split("(").length;
    const close = exp.split(")").length;

    if (open !== close) {
      exp += ")";
      exp = exp.replace("()", "");
    }

    if (exp === "5/(55+5)") {
      console.log("???", evalPostfix("5/(55+5)", number, N));
    }
    // answer = Math.min(answer, evalPostfix(exp, number, N));
  }

  return answer;
}

solution(N, number);

let i = 10;

그래서 후위식으로 변환해서 푸는 방식을 고려해봤다. 

 

이번에는 문제는 풀렸는데, 재귀식으로 사용하는 것 자체가 경우의 수가 너무 많아서 

한번 실행하면 몇 십분이 걸리는 문제가 발생했다. 

 

const N = 5;
const number = 55555555;

function solution(N, number) {
  let answer = -1;
  const set = Array.from(new Array(9), () => new Set());

  for (let i = 1; i <= 8; i++) {
    set[i].add(parseInt(N.toString().repeat(i)));

    for (let j = i; j > 0; j--) {
      for (let item of set[i - j]) {
        for (let item2 of set[j]) {
          set[i].add(parseInt(item + item2));
          set[i].add(parseInt(item - item2));
          set[i].add(parseInt(item * item2));
          set[i].add(parseInt(item / item2));
        }
      }
    }

    if (set[i].has(number)) {
      answer = i;
      break;
    }
  }

  return answer;
}

solution(N, number);

솔직히 이 방식은 힌트를 받고 문제를 풀었는데, 

N이란 숫자와 사칙연산을 활용해서 결과를 도출할 때는, 

 

N을 1개 쓸때는 5,

N을 2개 쓸때는 55와 N1 과 N1을 사칙연산,

N을 3개 쓸때는 555와 N1 과 N2를 사칙연산, N2와 N1을 사칙연산,

N을 4개 쓸때는 5555와 N1 과 N3를 사칙연산, N3 와 N1을 사칙연산, N2 와 N2를 사칙연산 

 

처럼 공식이 있었다. 

 

공식을 알아내니 쉽게 코딩을 할 수 있었다. 

Array에 Set을 넣어준 이유는 중복된 값을 하나로 만들어 사칙연산을 할 때 조금이라도 빨라지게 하기 위해서 사용했다. 

 

이번 문제를 푸는데, 오전 11시부터 6시까지 총 7시간이 걸렸다. 

물론 중간에 물, 화장실 등 사용한 시간이 있었지만 처음으로 알고리즘 문제를 푸는데 벽을 느끼게 되었다. 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges