[카카오 인턴] 수식 최대화

문제 링크

문제 요약

input

숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식

output

전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.

1. 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 한다.
2. 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출

해결방법

두 가지 방법이 떠오는데 둘 다 스택을 사용하는 방법이다.

후위표기식을 이용한 방법으로 풀이를 시도해본다.

1. 주어진 연산자들로 조합을 만든다. (3! = 6)
2. 연산한다.
   1. 후위표기법으로 변환한다
      1. 변환시 매개변수로 우선순위를 받아서 각각 다른 우선순위로 후위표기법을 만든다
   2. 계산한다.
3. 반환 값의 절대값 중 가장 큰 값을 리턴한다.

과정은 쉬운데 구현에 꽤나 힘이 들었다.

오랜만에 후위표기법을 사용해보았다.

소스코드

최초

function getCases(opers: string[]): Set<{ [operator: string]: number }> {
  const cases = new Set<{ [operator: string]: number }>()
  for (let i = 0; i < opers.length; i++) {
    for (let j = 0; j < opers.length; j++) {
      for (let k = 0; k < opers.length; k++) {
        if (i !== j && j !== k && i !== k) {
          cases.add({ '*': i, '-': j, '+': k })
        }
      }
    }
  }
  return cases
}

const postFix = (
  splittedExp: string[],
  operator: { [operator: string]: number }
): number => {
  const stack: string[] = []
  const result = []

  splittedExp.forEach((elem) => {
    if (!Number.isNaN(parseInt(elem))) {
      result.push(parseInt(elem))
    } else {
      while (stack.length) {
        if (operator[elem] <= operator[stack[stack.length - 1]]) {
          result.push(stack.pop())
        } else {
          break
        }
      }
      stack.push(elem)
    }
  })

  while (stack.length) {
    result.push(stack.pop())
  }

  const numStack: number[] = []

  result.forEach((elem) => {
    if (typeof elem == 'number') {
      numStack.push(elem)
    } else {
      const num2: number = numStack.pop()
      const num1: number = numStack.pop()
      switch (elem) {
        case '+':
          numStack.push(num1 + num2)
          break
        case '-':
          numStack.push(num1 - num2)
          break
        case '*':
          numStack.push(num1 * num2)
          break
      }
    }
  })

  return numStack[0]
}

function solution(expression: string): number {
  const operators = ['*', '+', '-']
  const cases = getCases(operators)
  const splittedExp = expression.split(/(\*|\-|\+)/)

  let max = 0
  cases.forEach((element) => {
    const result = Math.abs(postFix(splittedExp, element))
    max = max < result ? result : max
  })

  return max
}
export default solution

개선

소스코드가 길고 가독성도 좋지 않다. 리팩토링을 하자.

function getCases(opers: string[]): Set<{ [operator: string]: number }> {
  const cases = new Set<{ [operator: string]: number }>()
  for (let i = 0; i < opers.length; i++)
    for (let j = 0; j < opers.length; j++)
      for (let k = 0; k < opers.length; k++)
        if (i !== j && j !== k && i !== k) {
          cases.add({ '*': i, '-': j, '+': k })
        }
  return cases
}

const postFix = (
  splittedExp: string[],
  operator: { [operator: string]: number }
): number => {
  const stack: string[] = []
  const result: (string | number)[] = []

  splittedExp.forEach((elem) => {
    const parsedElem = parseInt(elem)
    if (!Number.isNaN(parsedElem)) {
      result.push(parsedElem)
    } else {
      // *|+|-
      while (stack.length) {
        if (operator[elem] <= operator[stack[stack.length - 1]]) {
          result.push(stack.pop())
        } else {
          break
        }
      }
      stack.push(elem)
    }
  })

  while (stack.length) {
    result.push(stack.pop())
  }

  const numStack: number[] = []

  result.forEach((elem) => {
    if (typeof elem == 'number') {
      numStack.push(elem)
    } else {
      const num2: number = numStack.pop()
      const num1: number = numStack.pop()
      switch (elem) {
        case '+':
          numStack.push(num1 + num2)
          break
        case '-':
          numStack.push(num1 - num2)
          break
        case '*':
          numStack.push(num1 * num2)
          break
      }
    }
  })
  return numStack[0]
}

function solution(expression: string): number {
  const operators = ['*', '+', '-']
  const cases = getCases(operators)
  const splittedExp = expression.split(/(\*|\-|\+)/)

  let max = 0
  cases.forEach((element) => {
    const result = Math.abs(postFix(splittedExp, element))
    max = max < result ? result : max
  })

  return max
}
export default solution