2020 카카오 인턴쉽 수식 최대화

연산자와 피연산자를 적절하게 나누는 것이 포인트였다. 나눴을 경우 문제의 조건에 따라 계산을 적용하기 수월했다. 나는 groupA, groupB로 나눴다. 

 

그 다음 연산자의 순서를 표현하기 위해 0을 *, 1을 +, 2를 -로 표현한 후 backTracking으로 순서를 표현했다. 

 

const map = {
    0: "*",
    1: "+",
    2: "-",
}
const visited = Array(3).fill(false)


function backTracking(curr) {
    if (curr.length === 3) {
      order.push(curr)
      return
    }

    for (let i = 0; i < 3; i++) {
      if (visited[i]) continue
      visited[i] = true
      backTracking([...curr, i])
      visited[i] = false
    }
}

 

순서를 모두 구한 후에는 연산자와 피연산자를 나누는 파싱을 했다.

 

const groupA = []
const groupB = []

while (true) {
  let i = 0
  while (numberString.includes(expression[i])) {
    i++
  }

  const temp = expression.slice(0, i)
  const operator = expression[i]

  if (!operator) {
    groupA.push(temp)
    break
  }

  groupA.push(+temp)
  groupB.push(operator)

  expression = expression.slice(i + 1)
}

 

파싱 후에는 연산자의 우선 순위에 따라 연산을 적용하는 과정을 거치면 답을 구할 수 있다.  전체 코드는 아래와 같다. 

 

function solution(expression) {
  let ans = -Infinity
  const numberString = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
  const order = []
  const visited = Array(3).fill(false)
  const map = {
    0: "*",
    1: "+",
    2: "-",
  }

  backTracking([])

  for (const o of order) {
    calculate(expression, o)
  }

  function calculate(expression, order) {
    // 피연산자와 연산자를 나누자
    const groupA = []
    const groupB = []

    while (true) {
      let i = 0
      while (numberString.includes(expression[i])) {
        i++
      }

      const temp = expression.slice(0, i)
      const operator = expression[i]

      if (!operator) {
        groupA.push(temp)
        break
      }

      groupA.push(+temp)
      groupB.push(operator)

      expression = expression.slice(i + 1)
    }

    const first = map[order[0]]
    const second = map[order[1]]
    const third = map[order[2]]

    let i = 0

    while (groupB.length) {
      const operator = i === 0 ? first : i === 1 ? second : third

      while (groupB.includes(operator)) {
        const index = groupB.indexOf(operator)
        const left = groupA[index]
        const right = groupA[index + 1]

        const result = eval(left + operator + right)
        groupA.splice(index, 2, result)
        groupB.splice(index, 1)
      }

      i++
    }

    ans = Math.max(ans, Math.abs(groupA[0]))
  }

  function backTracking(curr) {
    if (curr.length === 3) {
      order.push(curr)
      return
    }

    for (let i = 0; i < 3; i++) {
      if (visited[i]) continue
      visited[i] = true
      backTracking([...curr, i])
      visited[i] = false
    }
  }

  return ans
}